답안 #138776

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138776 2019-07-30T10:15:58 Z popovicirobert Queue (CEOI06_queue) C++14
86 / 100
1000 ms 51060 KB
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44


/*const int MOD = (int) 1e9 + 7;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}*/

/*int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}*/

using namespace std;

const int INF = 1e9;

map <int, int> prv, nxt;

inline void fix(int a) {
    if(prv[a] == 0) {
        prv[a] = a - 1;
    }
    if(nxt[a] == 0) {
        nxt[a] = a + 1;
    }
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, q;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for(i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        fix(a), fix(b);

        int x = prv[a], y = nxt[a];
        fix(x), fix(y);
        nxt[x] = y;
        prv[y] = x;

        fix(prv[b]);
        nxt[prv[b]] = a;
        prv[a] = prv[b];
        nxt[a] = b;
        prv[b] = a;
    }

    vector <int> all;
    for(auto it : nxt) {
        if(it.first > 0)
            all.push_back(it.first);
    }
    for(auto it : prv) {
        if(it.first > 0)
            all.push_back(it.first);
    }

    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());

    map <int, bool> vis;
    for(auto it : all) {
        vis[it] = 1;
    }

    vector < pair <int, int> > aux;
    for(auto it : all) {
        //cerr << it << " " << prv[it] << " " << nxt[it] << "\n";
        if(vis[prv[it]] == 0) {
            aux.push_back({prv[it], it});
        }
    }

    sort(aux.begin(), aux.end());

    map <int, int> id, pos;
     // id[x] = cine se afla la x
     // pos[x] = la ce pos e x

    vector < pair <int, int> > len;
    vector <int> sp;
    int last = 1, sum = 0;

    for(auto it : aux) {
        len.push_back({last, prv[it.second]});
        sum += prv[it.second] - last + 1;
        sp.push_back(sum);

        int cur = it.second;
        while(vis[cur]) {

            sum++;
            pos[cur] = sum, id[sum] = cur;

            cur = nxt[cur];
        }

        last = cur;
    }

    len.push_back({last, INF});
    sum += INF - last + 1;
    sp.push_back(sum);

    cin >> q;

    while(q--) {
        char ch;
        int x;

        cin >> ch >> x;

        if(ch == 'P') {
            if(pos[x] != 0) {
                cout << pos[x] << "\n";
                continue;
            }
            int p = upper_bound(len.begin(), len.end(), make_pair(x, INF)) - len.begin() - 1;
            cout << sp[p] - (len[p].second - x) << "\n";
        }
        else {
            if(id[x] != 0) {
                cout << id[x] << "\n";
                continue;
            }
            int p = lower_bound(sp.begin(), sp.end(), x) - sp.begin();
            cout << len[p].second - (sp[p] - x) << "\n";
        }
    }

    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 8 ms 1016 KB Output is correct
5 Correct 65 ms 5084 KB Output is correct
6 Correct 101 ms 7752 KB Output is correct
7 Correct 117 ms 7808 KB Output is correct
8 Correct 229 ms 15952 KB Output is correct
9 Correct 288 ms 16316 KB Output is correct
10 Correct 288 ms 17820 KB Output is correct
11 Correct 742 ms 35248 KB Output is correct
12 Correct 546 ms 21012 KB Output is correct
13 Partially correct 743 ms 35104 KB Partially correct
14 Correct 774 ms 35488 KB Output is correct
15 Correct 747 ms 35368 KB Output is correct
16 Correct 753 ms 35252 KB Output is correct
17 Correct 47 ms 2168 KB Output is correct
18 Correct 96 ms 4124 KB Output is correct
19 Correct 140 ms 4584 KB Output is correct
20 Correct 262 ms 8304 KB Output is correct
21 Incorrect 653 ms 36228 KB Output isn't correct
22 Correct 832 ms 39196 KB Output is correct
23 Execution timed out 1068 ms 50976 KB Time limit exceeded
24 Execution timed out 1051 ms 51060 KB Time limit exceeded
25 Correct 691 ms 27116 KB Output is correct