Submission

Score: 100

User: KantaponZ

Problemset: ร้านปลอดภาษี (Duty Free)

Language: cpp

Time: 0.343 second

Submitted On: 2025-07-08 20:37:03

#include <bits/stdc++.h>
using namespace std;
#define M max_allowed_positions

int ct;
vector<int> v;
int pa[2000006];
bool u[2000005];

int fp(int n) {
    if (pa[n] == n) {
        return n;
    }
    return pa[n] = fp(pa[n]);
}

void unite(int x, int y) {
    int px = fp(x), py = fp(y);
    pa[x] = min(px, py);
    pa[y] = pa[x];
}

int minimum_bag_rearrangement_time(vector<int> max_allowed_positions) {
    
    int N = max_allowed_positions.size();
    v.resize(N + 1);
    for (int i = 1; i <= N; i++) {
        pa[i] = i;
    }

    for (int i = 1; i <= N; i++) {
        if (u[M[i - 1]] == 0) {
            u[M[i - 1]] = 1;
            v.emplace_back(M[i - 1]);
            if (u[M[i - 1] - 1]) unite(M[i - 1] - 1, M[i - 1]);
            if (u[M[i - 1] + 1]) unite(M[i - 1] + 1, M[i - 1]);
            //cout << M[i - 1] << " PASS\n";
        } else {
            int y = fp(M[i - 1]) - 1;
            if (y > 0) {
                u[y] = 1;
                v.emplace_back(y);
                if (u[y - 1]) unite(y - 1, y);
                if (u[y + 1]) unite(y + 1, y);
                //cout << M[i - 1] << " " << y << " PASS\n";
            } else {
                ct++;
                for (auto x : v) {
                    u[x] = 0;
                    pa[x] = x;
                }
                v.clear();
                u[M[i - 1]] = 1;
                v.emplace_back(M[i - 1]);
                //cout << M[i - 1] << " Failed\n";
            }
        }
    }
        
    return ct;
}

/*

5
1 2 3 4 5

5 
1 3 3 2 3

*/







/*
int main() {
    std::cin.tie(0);
    std::ios_base::sync_with_stdio(0);
    int nBag;
    std::cin >> nBag;
    std::vector<int> max_allowed_positions(nBag);
    for (auto &max_allowed_position: max_allowed_positions) {
        std::cin >> max_allowed_position;
    }
    std::cout << minimum_bag_rearrangement_time(max_allowed_positions);
    return 0;
}
    */