Submission

Score: 100

User: NovemNotes

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

Language: cpp

Time: 0.353 second

Submitted On: 2026-04-24 16:04:38

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

struct DSU{
    int n,timer=1;
    vector<int> head,lazy;
    DSU(int s){
        n = s;
        head.assign(n+9,0);
        lazy.assign(n+9,0);
        for(int i=1;i<=n;i++){
            head[i] = i;
        }
    }
    void pushlz(int i){
        if(lazy[i] != timer){
            lazy[i] = timer;
            head[i] = i;
        }
    }
    int findhead(int n){
        pushlz(n);
        return (head[n] == n ? n : head[n] = findhead(head[n]));
    }
    int merge(int a,int b){
        int ha = findhead(a) , hb = findhead(b);
        if(ha==hb)return false;
        head[ha] = hb;
        return true;
    }
    void reset(){
        timer++;
    }
};

int minimum_bag_rearrangement_time(vector<int> vec){
    int ans=0;
    int n = vec.size();
    DSU dsu(n);
    for(auto &x:vec){
        int h = dsu.findhead(x);
        if(h==0){
            dsu.reset();
            ans++;
        }
        h = dsu.findhead(x);
        // cout << x << " " << h << "\n";
        dsu.merge(h,h-1);
    }
    return ans;
}

// int32_t main(){
//     ios_base::sync_with_stdio(false);cin.tie(NULL);
//     vector<int> v = {1,1,1,1,3,3,3,3,3,4};
//     cout << minimum_bag_rearrangement_time(v) << "\n";
//     return 0;
// }
/*
5
1 2 3 4 5
*/