Submission #138790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138790	2019-07-30T10:27:49 Z	popovicirobert	Queue (CEOI06_queue)	C++14	92 / 100	1000 ms	50072 KB

queue

#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(a == 1)
            prv[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;
    }

    map <int, bool> vis;
    for(auto &it : nxt) {
        if(it.first > 0)
            vis[it.first] = 1;
    }
    for(auto &it : prv) {
        if(it.second == -1) {
            it.second = 0;
        }
        if(it.first > 0)
            vis[it.first] = 1;
    }

    vector < pair <int, int> > aux;
    for(auto &it : nxt) {
        if(vis[prv[it.first]] == 0) {
            aux.push_back({prv[it.first], it.first});
        }
    }
    for(auto &it : prv) {
        if(vis[prv[it.first]] == 0) {
            aux.push_back({prv[it.first], it.first});
        }
    }

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

    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;
}

Subtask #1

92.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	4 ms	380 KB	Output is correct
4	Correct	9 ms	1016 KB	Output is correct
5	Correct	60 ms	5072 KB	Output is correct
6	Correct	97 ms	7676 KB	Output is correct
7	Correct	120 ms	7544 KB	Output is correct
8	Correct	244 ms	15708 KB	Output is correct
9	Correct	267 ms	16240 KB	Output is correct
10	Correct	295 ms	17448 KB	Output is correct
11	Correct	807 ms	34580 KB	Output is correct
12	Correct	609 ms	20252 KB	Output is correct
13	Correct	813 ms	34648 KB	Output is correct
14	Correct	867 ms	34820 KB	Output is correct
15	Correct	869 ms	34912 KB	Output is correct
16	Correct	816 ms	34796 KB	Output is correct
17	Correct	48 ms	2168 KB	Output is correct
18	Correct	95 ms	4124 KB	Output is correct
19	Correct	147 ms	4600 KB	Output is correct
20	Correct	276 ms	8056 KB	Output is correct
21	Correct	734 ms	35552 KB	Output is correct
22	Correct	852 ms	38640 KB	Output is correct
23	Execution timed out	1073 ms	50072 KB	Time limit exceeded
24	Execution timed out	1082 ms	46868 KB	Time limit exceeded
25	Correct	892 ms	26580 KB	Output is correct