Submission #976050

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
976050	2024-05-06T06:24:57 Z	Double_Slash	Queue (CEOI06_queue)	C++17	88 / 100	218 ms	37864 KB

queue

#include <bits/stdc++.h>
#define debug(x) [&]() { auto _x = x; cerr << __LINE__ << ": " << #x << " = " << _x << endl; }()
 
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[*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:64:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Block>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |                 if (i + (1 << j) < arr.size()) {
      |                     ~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1

88.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	3 ms	348 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Runtime error	9 ms	2392 KB	Execution killed with signal 11
6	Correct	99 ms	3468 KB	Output is correct
7	Runtime error	45 ms	7188 KB	Execution killed with signal 11
8	Correct	119 ms	7288 KB	Output is correct
9	Correct	113 ms	7624 KB	Output is correct
10	Correct	122 ms	8404 KB	Output is correct
11	Correct	98 ms	17964 KB	Output is correct
12	Correct	80 ms	16072 KB	Output is correct
13	Correct	108 ms	18372 KB	Output is correct
14	Correct	116 ms	19400 KB	Output is correct
15	Correct	126 ms	18884 KB	Output is correct
16	Correct	112 ms	19100 KB	Output is correct
17	Correct	57 ms	1372 KB	Output is correct
18	Correct	65 ms	2388 KB	Output is correct
19	Correct	102 ms	3080 KB	Output is correct
20	Correct	133 ms	4516 KB	Output is correct
21	Correct	128 ms	19224 KB	Output is correct
22	Runtime error	136 ms	37864 KB	Execution killed with signal 11
23	Correct	218 ms	24776 KB	Output is correct
24	Correct	218 ms	24768 KB	Output is correct
25	Correct	193 ms	20664 KB	Output is correct