Submission #683004

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683004	2023-01-17T13:31:42 Z	Ahmed57	Queue (CEOI06_queue)	C++14	100 / 100	281 ms	19672 KB

queue

#include <bits/stdc++.h>

using namespace std;
#define int long long
map<int,int> nex,pre;
int next(int x){
    if(nex.count(x))return nex[x];
    return x+1;
}int prev(int x){
    if(pre.count(x))return pre[x];
    return x-1;
}
int inf = 1e9;
signed main(){
    int val = 1;
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        if(a==val){
            val=next(a);
        }
        if(b==val){
            val= a;
        }
        nex[prev(a)] = next(a);
        pre[next(a)] = prev(a);
        int la = prev(b);
        nex[la] = a;
        pre[a] = la;
        nex[a] = b;
        pre[b] = a;
    }
    nex[inf] = inf+1;
    vector<pair<int,int>> v;
    if(val==1&&nex[1]==0){
        nex[1] = 2;
    }
    while(1){
        if(val==inf)break;
        if(!nex.count(val)){
            auto pp = nex.lower_bound(val+1);
            long long ne = (*pp).first;
            v.push_back({val,ne-val});
            val = ne;
            continue;
        }else{
            long long ne= nex[val];
            v.push_back({val,1});
            val= ne;
            continue;
        }
    }
    int q;cin>>q;
    set<pair<long long,long long>> L,R;
    for(int i = 0;i<q;i++){
        char c;cin>>c;
        long long x;cin>>x;
        if(c=='L'){
            L.insert({x,i});
        }else{
            R.insert({x,i});
        }
    }
    v.push_back({inf,1});
    long long ans[q] = {0};
    int st = 0, cur = 1;
    for(auto i:L){
        while(st<v.size()-1&&cur+v[st].second<=i.first)cur+=v[st].second,st++;
        ans[i.second] = v[st].first+(i.first-cur);
    }
    long long sum = 1;
    for(int i = 0;i<v.size();i++){
        if(v[i].second==1){
            pair<int,int> p = {v[i].first,0};
            auto it = R.lower_bound(p);
            while(it!=R.end()&&(*it).first==v[i].first){
                ans[(*it).second] = sum;
                it++;
            }
        }else{
            int l = v[i].first , r = v[i].second+v[i].first-1;
            pair<int,int> p = {l,0};
            auto it = R.lower_bound(p);
            while(it!=R.end()&&(*it).first<=r){
                ans[(*it).second] = sum+((*it).first-l);
                it++;
            }
        }
        sum+=v[i].second;
    }
    for(int i = 0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:70:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         while(st<v.size()-1&&cur+v[st].second<=i.first)cur+=v[st].second,st++;
      |               ~~^~~~~~~~~~~
queue.cpp:74:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Correct	4 ms	468 KB	Output is correct
5	Correct	45 ms	4748 KB	Output is correct
6	Correct	52 ms	5608 KB	Output is correct
7	Correct	67 ms	6388 KB	Output is correct
8	Correct	85 ms	8148 KB	Output is correct
9	Correct	82 ms	8432 KB	Output is correct
10	Correct	88 ms	8828 KB	Output is correct
11	Correct	209 ms	11764 KB	Output is correct
12	Correct	195 ms	10044 KB	Output is correct
13	Correct	211 ms	12048 KB	Output is correct
14	Correct	247 ms	12280 KB	Output is correct
15	Correct	209 ms	12340 KB	Output is correct
16	Correct	212 ms	12484 KB	Output is correct
17	Correct	52 ms	1836 KB	Output is correct
18	Correct	69 ms	3216 KB	Output is correct
19	Correct	101 ms	4352 KB	Output is correct
20	Correct	156 ms	5784 KB	Output is correct
21	Correct	169 ms	13308 KB	Output is correct
22	Correct	206 ms	16188 KB	Output is correct
23	Correct	277 ms	19672 KB	Output is correct
24	Correct	281 ms	19672 KB	Output is correct
25	Correct	277 ms	15804 KB	Output is correct