Submission

Score: 4

User: GGEZLOLx3D

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

Language: cpp

Time: 0.615 second

Submitted On: 2026-03-26 20:40:38

#include<bits/stdc++.h>
#include "duty_free.h"
using namespace std;
int mxre=0;
int seg[8000100];
int n;
vector<bool> ch;
void bud(int node,int l,int r){
    if(l==r){
        if(!ch[l]){
            seg[node]=l;
            mxre=max(mxre,node);
            return ;
        }
        else{
            seg[node]=0;
            mxre=max(mxre,node);
            return ;
        }
    }
    int mid=(l+r)>>1;
    bud(node*2,l,mid);
    bud(node*2+1,mid+1,r);
    seg[node]=max(seg[node*2],seg[node*2+1]);
    return ;
}
void upd(int node,int l,int cl,int cr,int ka){
    if(cl>l||cr<l){
        return ;
    }
    if(cl==l&&cr==l){
        if(ka==1){
            seg[node]=0;
        }
        else{
            seg[node]=l;
        }
        return ;
    }
    int mid=(cl+cr)>>1;
    upd(node*2,l,cl,mid,ka);
    upd(node*2+1,l,mid+1,cr,ka);
    seg[node]=max(seg[node*2],seg[node*2+1]);
    return ;
}
int can(int node,int l,int r,int cl,int cr){
    if(cl>r||cr<l){
        return 0;

    }
    if(cl>=l&&cr<=r){
        return seg[node];
    }
    int mid=(cl+cr)/2;
    int js=can(node*2,l,r,cl,mid);
    int jk=can(node*2+1,l,r,mid+1,cr);
    return max(js,jk);
}
// you can write more function here
int minimum_bag_rearrangement_time(vector<int> mapo) {
    n=mapo.size();
    vector<bool> mp(n+1,false);
    ch=move(mp);
    vector<int> res;
    int c=0,i,j;
    bud(1,1,n);
    for(i=0;i<n;i++){
        if(!ch[mapo[i]]){
            ch[mapo[i]]=true;
            upd(1,mapo[i],1,n,1);
            res.push_back(mapo[i]);
        }
        else{

            int ma=can(1,1,mapo[i],1,n);
            if(ma==0){
                c++;
                for(j=0;j<res.size();j++){
                    ch[res[j]]=false;
                    upd(1,ma,1,n,0);
                }
                res.clear();
                ch[mapo[i]]=true;
                upd(1,ma,1,n,1);
                res.push_back(mapo[i]);

            }
            else{
                ch[ma]=true;
                upd(1,ma,1,n,1);
                res.push_back(ma);
            }
        }
    }
  return c;
}