Submission #682994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
682994	2023-01-17T12:56:01 Z	Ahmed57	Queue (CEOI06_queue)	C++14	66 / 100	261 ms	16052 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(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	0 ms	212 KB	Output is correct
2	Correct	0 ms	300 KB	Output is correct
3	Correct	2 ms	340 KB	Output is correct
4	Partially correct	5 ms	492 KB	Partially correct
5	Correct	49 ms	4396 KB	Output is correct
6	Correct	53 ms	4984 KB	Output is correct
7	Correct	64 ms	5696 KB	Output is correct
8	Correct	73 ms	7032 KB	Output is correct
9	Partially correct	82 ms	7240 KB	Partially correct
10	Partially correct	95 ms	7536 KB	Partially correct
11	Correct	177 ms	9400 KB	Output is correct
12	Correct	178 ms	7780 KB	Output is correct
13	Correct	242 ms	9828 KB	Output is correct
14	Incorrect	167 ms	9532 KB	Output isn't correct
15	Incorrect	209 ms	9464 KB	Output isn't correct
16	Correct	198 ms	10204 KB	Output is correct
17	Correct	46 ms	2216 KB	Output is correct
18	Incorrect	65 ms	3324 KB	Output isn't correct
19	Partially correct	102 ms	4300 KB	Partially correct
20	Incorrect	157 ms	6004 KB	Output isn't correct
21	Incorrect	157 ms	10488 KB	Output isn't correct
22	Correct	213 ms	12984 KB	Output is correct
23	Correct	260 ms	16052 KB	Output is correct
24	Incorrect	261 ms	15436 KB	Output isn't correct
25	Partially correct	253 ms	13472 KB	Partially correct