Submission #976071

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976071	2024-05-06T07:03:21 Z	Double_Slash	Queue (CEOI06_queue)	C++17	100 / 100	284 ms	19420 KB

queue

#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int, int> pint;
 
const int INF = 1e9;
int n, q;
struct Block {
    int l, r;
    int sum = 0;
    Block *lc = nullptr, *rc = nullptr;
};
 
int main() {
    cin >> n;
    vector<pint> swaps(n);
    set<int> used;
    for (auto &[a, b]: swaps) {
        cin >> a >> b;
        used.emplace(a);
        used.emplace(b);
    }
    int last = 1;
    auto root = new Block{1, 0};
    auto join = [] (Block *a, Block *b) {
        if (a) a->rc = b;
        if (b) b->lc = a;
    };
    map<int, Block*> m;
    auto ptr = root;
    auto add = [&] (int l, int r) {
        join(ptr, m[r] = new Block{l, r});
        ptr = ptr->rc;
    };
    for (int x: used) {
        if (x > last) add(last, x - 1);
        add(x, x);
        last = x + 1;
    }
    if (last <= INF) add(last, INF);
    for (auto [a, b]: swaps) {
        auto blocka = m[a], blockb = m[b];
        join(blocka->lc, blocka->rc);
        join(blockb->lc, blocka);
        join(blocka, blockb);
    }
    vector<Block*> arr;
    for (; root->rc; root = root->rc) {
        root->rc->sum = root->sum + root->r - root->l + 1;
        arr.push_back(root->rc);
    }
    cin >> q;
    while (q--) {
        char c;
        int x;
        cin >> c >> x;
        if (c == 'P') {
            auto b = used.count(x) ? m[x] : m[x > *prev(used.end()) ? INF : (*used.upper_bound(x) - 1)];
            cout << b->sum + x - b->l + 1 << endl;
        } else {
            int i = 0;
            for (int j = 20; --j >= 0;) {
                if (i + (1 << j) < arr.size()) {
                    if (arr[i + (1 << j)]->sum < x) i += 1 << j;
                }
            }
            cout << arr[i]->l + x - arr[i]->sum - 1 << endl;
        }
    }
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:63:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Block*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                 if (i + (1 << j) < arr.size()) {
      |                     ~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	2 ms	348 KB	Output is correct
4	Correct	5 ms	604 KB	Output is correct
5	Correct	88 ms	1764 KB	Output is correct
6	Correct	99 ms	2412 KB	Output is correct
7	Correct	107 ms	3792 KB	Output is correct
8	Correct	120 ms	5572 KB	Output is correct
9	Correct	148 ms	6112 KB	Output is correct
10	Correct	135 ms	6600 KB	Output is correct
11	Correct	104 ms	13260 KB	Output is correct
12	Correct	89 ms	11416 KB	Output is correct
13	Correct	127 ms	13380 KB	Output is correct
14	Correct	133 ms	13272 KB	Output is correct
15	Correct	134 ms	13420 KB	Output is correct
16	Correct	137 ms	13520 KB	Output is correct
17	Correct	46 ms	752 KB	Output is correct
18	Correct	72 ms	1412 KB	Output is correct
19	Correct	104 ms	2028 KB	Output is correct
20	Correct	162 ms	2644 KB	Output is correct
21	Correct	161 ms	13824 KB	Output is correct
22	Correct	221 ms	16072 KB	Output is correct
23	Correct	284 ms	19420 KB	Output is correct
24	Correct	255 ms	19144 KB	Output is correct
25	Correct	233 ms	14824 KB	Output is correct