Submission #138776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138776	2019-07-30T10:15:58 Z	popovicirobert	Queue (CEOI06_queue)	C++14	86 / 100	1000 ms	51060 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(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;
}

Subtask #1

86.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	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