Submission #683003

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683003	2023-01-17T13:26:07 Z	Ahmed57	Queue (CEOI06_queue)	C++14	88 / 100	297 ms	19664 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);
            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: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

88.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	4 ms	452 KB	Partially correct
5	Correct	47 ms	4632 KB	Output is correct
6	Correct	58 ms	5548 KB	Output is correct
7	Correct	66 ms	6356 KB	Output is correct
8	Correct	74 ms	8108 KB	Output is correct
9	Partially correct	80 ms	8364 KB	Partially correct
10	Partially correct	90 ms	9020 KB	Partially correct
11	Correct	192 ms	11828 KB	Output is correct
12	Correct	175 ms	10128 KB	Output is correct
13	Correct	200 ms	11980 KB	Output is correct
14	Partially correct	233 ms	12224 KB	Partially correct
15	Correct	206 ms	12388 KB	Output is correct
16	Correct	214 ms	12484 KB	Output is correct
17	Correct	42 ms	1836 KB	Output is correct
18	Correct	67 ms	3184 KB	Output is correct
19	Partially correct	109 ms	4232 KB	Partially correct
20	Correct	161 ms	5884 KB	Output is correct
21	Correct	160 ms	13432 KB	Output is correct
22	Correct	199 ms	16036 KB	Output is correct
23	Correct	297 ms	19664 KB	Output is correct
24	Correct	283 ms	19656 KB	Output is correct
25	Partially correct	245 ms	15856 KB	Partially correct