Submission #138786

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138786	2019-07-30T10:24:03 Z	popovicirobert	Queue (CEOI06_queue)	C++14	92 / 100	1000 ms	49516 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;
    }

    vector <int> all;
    for(auto it : nxt) {
        if(it.first > 0)
            all.push_back(it.first);
    }
    for(auto &it : prv) {
        if(it.second == -1) {
            it.second = 0;
        }
        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

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	376 KB	Output is correct
4	Correct	10 ms	1016 KB	Output is correct
5	Correct	66 ms	4600 KB	Output is correct
6	Correct	99 ms	7116 KB	Output is correct
7	Correct	120 ms	7032 KB	Output is correct
8	Correct	222 ms	14964 KB	Output is correct
9	Correct	284 ms	15580 KB	Output is correct
10	Correct	265 ms	16880 KB	Output is correct
11	Correct	788 ms	34064 KB	Output is correct
12	Correct	629 ms	20208 KB	Output is correct
13	Correct	714 ms	34160 KB	Output is correct
14	Correct	716 ms	34416 KB	Output is correct
15	Correct	734 ms	34256 KB	Output is correct
16	Correct	849 ms	34232 KB	Output is correct
17	Correct	51 ms	1528 KB	Output is correct
18	Correct	93 ms	3448 KB	Output is correct
19	Correct	139 ms	3676 KB	Output is correct
20	Correct	246 ms	6648 KB	Output is correct
21	Correct	754 ms	35100 KB	Output is correct
22	Correct	831 ms	37916 KB	Output is correct
23	Execution timed out	1010 ms	49516 KB	Time limit exceeded
24	Execution timed out	1039 ms	49468 KB	Time limit exceeded
25	Correct	700 ms	25480 KB	Output is correct