Submission #1153456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153456		m5588ohammed	Queue (CEOI06_queue)	C++20	50 / 100	560 ms	38032 KiB

queue

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
vector <array<int,2>> query1,query2;
vector <int> act,qu;
map <int,int> pos,vis,f,b,fw,bw,mp;
int n,q;
void ins(int x){
    if(vis[x]==0) act.push_back(x);
    vis[x]=1;
    return;
}
void build(){
    sort(act.begin(),act.end());
    for(int i=0;i<act.size();i++){
        //cout<<act[i]<<" ";
        pos[act[i]]=act[i];
        if(i!=0){
            f[act[i]]=act[i-1];
            fw[act[i]]=act[i]-act[i-1]-1;
        }
        else{
            b[0]=act[i];
            fw[act[i]]=bw[0]=act[i]-1;
        }
        if(i!=act.size()-1){
            b[act[i]]=act[i+1];
            bw[act[i]]=act[i+1]-act[i]-1;
        }
        else{
          bw[act[i]]=fw[1e9+1]=1e9-act[i];
          b[act[i]]=1e9+1;
        }
    }
    for(auto [A,B]:query1){
        int BACK=b[A],FRONT=f[A];
        b[FRONT]=BACK;
        f[BACK]=FRONT;
        bw[FRONT]=fw[BACK]=bw[A]+fw[A];
        FRONT=f[B];
        b[FRONT]=A;
        f[A]=FRONT;
        b[A]=B;
        f[B]=A;
        fw[A]=bw[FRONT];
        bw[A]=fw[B]=0;
    }
    int bg=b[0],sum=bw[0],idx=0;
    while(bg!=1e9+1){
        qu.push_back(bg);
        pos[bg]=sum+1;
        mp[sum+1]=bg;
        sum+=bw[bg]+1;
        bg=b[bg];
    }
    return;
}
int order(int i){
    int l=0,r=qu.size()-1,j=i-qu.size();
    while(l<=r){
        int mid=(l+r)/2;
        if(pos[qu[mid]]<=i){
            j=i-(mid+1);
            l=mid+1;
        }
        else r=mid-1;
    }
    return j;
}
int calc(int i){
    int l=1,r=1e9,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(mid-(upper_bound(act.begin(),act.end(),mid)-act.begin())<=i){
            ans=mid;
            l=mid+1;
        } 
        else r=mid-1;   
    }
    return ans;
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        query1.push_back({a,b});
        ins(a);
        ins(b);
    }
    cin>>q;
    for(int i=0;i<q;i++){
        char c;
        int x;
        cin>>c>>x;
        if(c=='L') query2.push_back({1,x});
        else{
            query2.push_back({2,x});
            ins(x);
        }
    }
    build();
    for(auto [a,b]:query2){
        if(a==2) cout<<pos[b]<<endl;
        else{
            if(mp[b]!=0) cout<<mp[b]<<endl;
            else{
                cout<<calc(order(b))<<endl;
            }
        }
    }
}  

• Subtask 1: 50 / 100