Submission #682999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
682999	2023-01-17T13:07:29 Z	Ahmed57	Queue (CEOI06_queue)	C++14	66 / 100	316 ms	19656 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;
        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<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()&&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);
            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:68: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]
   68 |         while(st<v.size()&&cur+v[st].second<=i.first)cur+=v[st].second,st++;
      |               ~~^~~~~~~~~
queue.cpp:72: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]
   72 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~
queue.cpp:37:10: warning: variable 'it' set but not used [-Wunused-but-set-variable]
   37 |     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	0 ms	212 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Partially correct	5 ms	468 KB	Partially correct
5	Correct	47 ms	4684 KB	Output is correct
6	Correct	50 ms	5576 KB	Output is correct
7	Correct	64 ms	6376 KB	Output is correct
8	Correct	82 ms	8120 KB	Output is correct
9	Partially correct	84 ms	8360 KB	Partially correct
10	Partially correct	89 ms	8896 KB	Partially correct
11	Correct	245 ms	11868 KB	Output is correct
12	Correct	174 ms	10044 KB	Output is correct
13	Correct	228 ms	11996 KB	Output is correct
14	Incorrect	204 ms	10900 KB	Output isn't correct
15	Incorrect	185 ms	11248 KB	Output isn't correct
16	Correct	224 ms	12372 KB	Output is correct
17	Correct	51 ms	1868 KB	Output is correct
18	Incorrect	65 ms	3124 KB	Output isn't correct
19	Partially correct	102 ms	4224 KB	Partially correct
20	Incorrect	154 ms	5492 KB	Output isn't correct
21	Incorrect	152 ms	12880 KB	Output isn't correct
22	Correct	225 ms	16068 KB	Output is correct
23	Correct	273 ms	19656 KB	Output is correct
24	Incorrect	316 ms	18668 KB	Output isn't correct
25	Partially correct	243 ms	15820 KB	Partially correct