Submission

Score: 100

User: mydKN

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

Language: cpp

Time: 0.358 second

Submitted On: 2025-06-27 23:28:48

#include<bits/stdc++.h>

using namespace std;

const int maxn = 2e6 + 5;

int pa[maxn], ver[maxn];
int curr = 1, res;

int findset(int u){
	if(ver[u] != curr){
		ver[u] = curr;
		pa[u] = u;
	}
	if(pa[u] == u) return u;
	return pa[u] = findset(pa[u]);
}

void unite(int u, int v){
	u = findset(u);
	v = findset(v);
	pa[u] = v;
}

int minimum_bag_rearrangement_time(vector<int> mxpos){
	int n = (int)mxpos.size();
	iota(pa, pa+n+1, 0);
	for(int i=0;i<n;++i){
		int p = findset(mxpos[i]);
		if(p == 0){
			++res;
			++curr;
			--i;
			continue;
		}
		unite(p, p-1);
	}
	return res;
}