Submission

Score: 5

User: kungarooo

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

Language: cpp

Time: 1.083 second

Submitted On: 2025-11-01 16:54:34

#include <bits/stdc++.h>
using namespace std;
// you can write more function here
#define N 22
struct segtree
{
  int seg[(1<<N)]={};
  void setzero(){
    memset(seg,0,sizeof(seg));
  }
  void update(int idx){
    idx+=(1<<(N-1));
    seg[idx]++;
    for(idx>>=1;idx>0;idx>>=1){
      seg[idx]=seg[idx*2]+seg[idx*2+1];
    }
  }
  int qry(int l,int r){
    l+=(1<<(N-1)),r+=(1<<(N-1))|1;
    int ans=0;
    for(;l<r;l>>=1,r>>=1){
      if(l&1)ans+=seg[l++];
      if(r&1)ans+=seg[--r];
    }
    return ans;
  }
};

int minimum_bag_rearrangement_time(vector<int> max_allowed_positions) {
  int sz=max_allowed_positions.size(),ans=0;
  segtree seg;
  //set<int> eridx;
  for(int i=0;i<sz;i++){
    if(seg.qry(1,max_allowed_positions[i])<max_allowed_positions[i]){
      seg.update(max_allowed_positions[i]);
      //eridx.insert(max_allowed_positions[i]);
    }else{
      ans++;
      seg.setzero();
      seg.update(max_allowed_positions[i]);
    }
  }
  return ans;
}