oj.uz

Submission #981553

# Submission time Handle Problem Language Result Execution time Memory
981553 2024-05-13T10:22:43 Z Ghetto Queue (CEOI06_queue) C++17
50 / 100
 321 ms 26204 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;
void precomp2() {
    int x = s, sum = 0;
    while (x != 0) {
        sum_before[x] = sum;
        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') {
            cout << 0 << '\n';
        } else {
            int y = *next(starts.upper_bound(x), -1);
            int ans = sum_before[y] + x - y + 1;
            cout << ans << '\n';
        }
    }

    
}

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 1 ms 348 KB Partially correct
3 Partially correct 2 ms 348 KB Partially correct
4 Partially correct 3 ms 788 KB Partially correct
5 Partially correct 94 ms 1824 KB Partially correct
6 Partially correct 95 ms 3308 KB Partially correct
7 Partially correct 113 ms 4528 KB Partially correct
8 Partially correct 104 ms 7016 KB Partially correct
9 Partially correct 113 ms 7520 KB Partially correct
10 Partially correct 113 ms 8044 KB Partially correct
11 Partially correct 114 ms 17328 KB Partially correct
12 Partially correct 76 ms 14564 KB Partially correct
13 Partially correct 119 ms 17416 KB Partially correct
14 Partially correct 134 ms 17384 KB Partially correct
15 Partially correct 142 ms 17540 KB Partially correct
16 Partially correct 165 ms 17488 KB Partially correct
17 Partially correct 50 ms 1384 KB Partially correct
18 Partially correct 64 ms 2252 KB Partially correct
19 Partially correct 96 ms 3280 KB Partially correct
20 Partially correct 130 ms 4348 KB Partially correct
21 Partially correct 130 ms 16520 KB Partially correct
22 Partially correct 178 ms 19344 KB Partially correct
23 Partially correct 254 ms 26204 KB Partially correct
24 Partially correct 321 ms 25940 KB Partially correct
25 Partially correct 177 ms 18972 KB Partially correct