oj.uz

Submission #981558

# Submission time Handle Problem Language Result Execution time Memory
981558 2024-05-13T10:30:46 Z Ghetto Queue (CEOI06_queue) C++17
100 / 100
 278 ms 29200 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using mii = unordered_map<int, int>;
const int N = 1e9;

vector<pii> moves;
set<int> starts = {1};
mii l, r, f;
int s;
void precomp1() {
    for (auto it = starts.begin(); it != starts.end(); it++) {
        l[*it] = (it == starts.begin()) ? 0 : *next(it, -1);
        r[*it] = (next(it, 1) == starts.end()) ? 0 : *next(it, 1);
        f[*it] = (next(it, 1) == starts.end()) ? N : *next(it, 1) - 1;
        // cout << *it << ": " << l[*it] << " " << r[*it] << " " << f[*it] << endl;
    }
    for (pii move : moves) {
        int x = move.first, y = move.second;
        r[l[x]] = r[x], l[r[x]] = l[x];
        l[x] = l[y], r[x] = y;
        r[l[y]] = x, l[y] = x;
    }
    for (int x : starts)
        if (l[x] == 0) s = x;
    // int x = s;
    // while (x != 0) {
    //     cout << x << " " << f[x] << '\n';
    //     x = r[x];
    // }
}
mii sum_before;
set<pii> sums;
void precomp2() {
    int x = s, sum = 0;
    while (x != 0) {
        sum_before[x] = sum, sums.insert({sum_before[x], x});
        sum += f[x] - x + 1;
        // cout << x << " " << f[x] << ": " << sum_before[x] << endl;
        x = r[x];
    }
}

int main() {
    // freopen("queue.in", "r", stdin), freopen("queue.out", "w", stdout);
    int m; cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y; cin >> x >> y;
        moves.push_back({x, y});
        for (int z : {x, x + 1, y})
            if (z <= N) starts.insert(z);
    }
    
    precomp1();
    precomp2();

    int q; cin >> q;
    for (int tc = 1; tc <= q; tc++) {
        char ch; cin >> ch;
        int x; cin >> x;
        if (ch == 'L') {
            int y = next(sums.lower_bound({x, -1}), -1)->second;
            int ans = y + x - sum_before[y] - 1;
            cout << ans << '\n';
        } else {
            int y = *next(starts.upper_bound(x), -1);
            int ans = sum_before[y] + x - y + 1;
            cout << ans << '\n';
        }
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 86 ms 1632 KB Output is correct
6 Correct 93 ms 2896 KB Output is correct
7 Correct 108 ms 4688 KB Output is correct
8 Correct 115 ms 7884 KB Output is correct
9 Correct 120 ms 8332 KB Output is correct
10 Correct 123 ms 8932 KB Output is correct
11 Correct 123 ms 19764 KB Output is correct
12 Correct 90 ms 16804 KB Output is correct
13 Correct 134 ms 20204 KB Output is correct
14 Correct 151 ms 19976 KB Output is correct
15 Correct 143 ms 20188 KB Output is correct
16 Correct 152 ms 19940 KB Output is correct
17 Correct 48 ms 728 KB Output is correct
18 Correct 69 ms 1852 KB Output is correct
19 Correct 98 ms 2604 KB Output is correct
20 Correct 143 ms 3800 KB Output is correct
21 Correct 150 ms 19196 KB Output is correct
22 Correct 190 ms 22244 KB Output is correct
23 Correct 278 ms 29200 KB Output is correct
24 Correct 274 ms 29188 KB Output is correct
25 Correct 217 ms 21476 KB Output is correct