Submission

Score: 0

User: njoop

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

Language: cpp

Time: 1.071 second

Submitted On: 2025-05-23 18:52:40

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define MAXN 2000005
#define MOD (int)(1e9+7)
#define INF (int)1e17
#define enl '\n'
//#define int long long
#define DB(code) cout<<'\t'<<code<<'\n';
#define SP <<' '<<
using namespace std;
int par[MAXN],sz[MAXN],mn[MAXN],used[MAXN];
int root(int i){
    return par[i]=(par[i]==i)?i:root(par[i]);
}
int join(int a,int b){
    if(sz[a]>=sz[b]){
        par[b]=a;
        sz[a]+=sz[b];
        mn[a]=min(mn[a],mn[b]);
    } else{
        par[a]=b;
        sz[b]+=sz[a];
        mn[b]=min(mn[a],mn[b]);
    }
}
int minimum_bag_rearrangement_time(std::vector<int> max_allowed_positions){
    int n=max_allowed_positions.size();
    vector<int> arr=max_allowed_positions;
    int ans=0,start=0;
    for(int i=0; i<n; i++) used[i]=-1;
    int i=0;
    while(i<n){
        int idx;
        if(used[arr[i]]<start) idx=arr[i];
        else idx=mn[root(arr[i])]-1;
        if(idx<0){
            start=i;
            ans++;
            continue;
        }
        if(used[idx]<start) par[idx]=mn[idx]=idx,sz[idx]=1,used[idx]=i;
        if(idx+1<n && used[idx+1]>=start) join(root(idx),root(idx+1));
        if(idx-1>=0 && used[idx-1]>=start) join(root(idx-1),root(idx));
        i++;
    }
    return ans;
}
/*signed main(){
    cin.tie(0)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++) cin >> arr[i],arr[i]--;
    int ans=minimum_bag_rearrangement_time(arr);
    cout << ans;
	return 0;
}*/

/*

12
2 4 3 5 3   1   1 3 3   2 4 1

10
1 1 1 2 1 1 2 2 2 1

*/