Submission #682995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
682995	2023-01-17T13:03:00 Z	Ahmed57	Queue (CEOI06_queue)	C++14	66 / 100	291 ms	14564 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});
        }
    }
    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:66: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]
   66 |         while(st<v.size()&&cur+v[st].second<=i.first)cur+=v[st].second,st++;
      |               ~~^~~~~~~~~
queue.cpp:70: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]
   70 |     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	1 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	45 ms	3844 KB	Output is correct
6	Correct	53 ms	4424 KB	Output is correct
7	Correct	71 ms	5016 KB	Output is correct
8	Correct	79 ms	6180 KB	Output is correct
9	Partially correct	87 ms	6360 KB	Partially correct
10	Partially correct	91 ms	6808 KB	Partially correct
11	Correct	178 ms	8380 KB	Output is correct
12	Correct	157 ms	7132 KB	Output is correct
13	Correct	238 ms	8600 KB	Output is correct
14	Incorrect	201 ms	8136 KB	Output isn't correct
15	Incorrect	175 ms	8388 KB	Output isn't correct
16	Correct	210 ms	8948 KB	Output is correct
17	Correct	44 ms	1576 KB	Output is correct
18	Incorrect	66 ms	2580 KB	Output isn't correct
19	Partially correct	97 ms	3276 KB	Partially correct
20	Incorrect	159 ms	4376 KB	Output isn't correct
21	Incorrect	160 ms	9468 KB	Output isn't correct
22	Correct	190 ms	11832 KB	Output is correct
23	Correct	291 ms	14564 KB	Output is correct
24	Incorrect	236 ms	13828 KB	Output isn't correct
25	Partially correct	233 ms	11700 KB	Partially correct