Submission

Score: 100

User: foldnut

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

Language: cpp

Time: 0.352 second

Submitted On: 2025-12-21 23:22:21

#include <bits/stdc++.h>
using namespace std;
const int N = 2000001;
vector<int> p(N), mn(N);
bool vs[N];
int _find(int x){
  if(x == p[x]) return x;
  return p[x] = _find(p[x]);
}
void _union(int x, int y){
  x = _find(x), y = _find(y);
  if(x != y){
    if(y < x) swap(x, y);
    p[y] = x;
    mn[x] = min(mn[x], mn[y]);
  }
}
int minimum_bag_rearrangement_time(std::vector<int> a) {
  int n = a.size(), ans = 0;
  iota(p.begin(), p.end(), 0);
  iota(mn.begin(), mn.end(), 0);
  vector<int> c;
  for(auto x : a){
    if(vs[x]){
      int m = mn[_find(x)] - 1;
      if(m == 0){
        ++ans;
        for(auto cc : c) vs[cc] = 0, p[cc] = cc, mn[cc] = cc;
        c.clear();
        vs[x] = 1;
        c.push_back(x);
      }else{
        vs[m] = 1;
        if(vs[m + 1]){
          _union(m, m + 1);
        }
        if(vs[m - 1]){
          _union(m - 1, m);
        }
        c.push_back(m);
      }
    }else{
      vs[x] = 1;
      if(vs[x + 1]){
        _union(x, x + 1);
      }
      if(vs[x - 1]){
        _union(x - 1, x);
      }
      c.push_back(x);
    }
  }
  return ans;
}