답안 #683003

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