답안 #682997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
682997 2023-01-17T13:04:46 Z Ahmed57 Queue (CEOI06_queue) C++14
66 / 100
247 ms 14356 KB
#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();
      |          ^~
# 결과 실행 시간 메모리 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