Submission #1153426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153426		m5588ohammed	Queue (CEOI06_queue)	C++20	50 / 100	400 ms	32048 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;
map <int,int> pos,vis,f,b,fw,bw;
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;
        }
    }
    //cout<<endl;
    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];
    while(bg!=0){
        pos[bg]=sum+1;
        sum+=bw[bg]+1;
        bg=b[bg];
    }
    return;
}
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 cout<<-1<<endl;
    }
}  

• Subtask 1: 50 / 100