Submission #682997

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
682997	2023-01-17T13:04:46 Z	Ahmed57	Queue (CEOI06_queue)	C++14	66 / 100	247 ms	14356 KB

queue

#include <bits/stdc++.h>

using namespace std;
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;
int main(){
    int val = 1;
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        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;
        if(b==val){
            val= a;
        }
    }
    nex[inf] = inf+1;
    vector<pair<int,int>> v;
    if(val==1&&nex[1]==0){
        nex[1] = 2;
    }
    auto it = nex.begin();
    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<int,int>> 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()&&cur+v[st].second<=i.first)cur+=v[st].second,st++;
        ans[i.second] = v[st].first+(i.first-cur);
    }
    int 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);
            if(it!=R.end()&&(*it).first==v[i].first){
                ans[(*it).second] = sum;
            }
        }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:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         while(st<v.size()&&cur+v[st].second<=i.first)cur+=v[st].second,st++;
      |               ~~^~~~~~~~~
queue.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
queue.cpp:36:10: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   36 |     auto it = nex.begin();
      |          ^~

Subtask #1

66.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Partially correct	3 ms	468 KB	Partially correct
5	Correct	46 ms	3728 KB	Output is correct
6	Correct	70 ms	4440 KB	Output is correct
7	Correct	62 ms	4928 KB	Output is correct
8	Correct	73 ms	6212 KB	Output is correct
9	Partially correct	78 ms	6360 KB	Partially correct
10	Partially correct	87 ms	6784 KB	Partially correct
11	Correct	179 ms	8372 KB	Output is correct
12	Correct	156 ms	7108 KB	Output is correct
13	Correct	181 ms	8640 KB	Output is correct
14	Incorrect	162 ms	8076 KB	Output isn't correct
15	Incorrect	176 ms	8352 KB	Output isn't correct
16	Correct	207 ms	9016 KB	Output is correct
17	Correct	41 ms	1576 KB	Output is correct
18	Incorrect	63 ms	2508 KB	Output isn't correct
19	Partially correct	96 ms	3272 KB	Partially correct
20	Incorrect	152 ms	4416 KB	Output isn't correct
21	Incorrect	145 ms	9540 KB	Output isn't correct
22	Correct	189 ms	11840 KB	Output is correct
23	Correct	247 ms	14356 KB	Output is correct
24	Incorrect	240 ms	13988 KB	Output isn't correct
25	Partially correct	226 ms	11708 KB	Partially correct