답안 #682999

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