Submission

Score: 100

User: Nagornz

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

Language: cpp

Time: 0.667 second

Submitted On: 2025-05-24 19:46:08

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define fix iota(par, par + N, 0ll)
#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define tiiii tuple <int, int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 2e6 + 5;

int i, pre, id[N], par[N];

int dsu(int a){ 
    if (id[a] <= pre) {
        id[a] = i;
        par[a] = a;
    }
    return par[a] = (par[a] == a ? a : dsu(par[a])); 
}

int32_t minimum_bag_rearrangement_time(vector <int32_t> a){
    int n = a.size(); pre = -1;
    fix; memset(id, -1, sizeof id);
    int ans = 0;
    for (i = 0; i < n; i++) {
        int x = dsu(a[i]);
        if (x <= 0) {
            ans++, pre = i - 1;
            x = dsu(a[i]);
        }
        par[x] = dsu(x - 1);
    }
    return ans;
}

// int32_t main(){
//     iShowSpeed;
//     int n; cin >> n;
//     vector <int32_t> a(n);
//     for (auto &e : a) cin >> e;
//     cout << minimum_bag_rearrangement_time(a);
// }