Submission #976071

#	Time	Username	Problem	Language	Result	Execution time	Memory
976071		Double_Slash	Queue (CEOI06_queue)	C++17	100 / 100	284 ms	19420 KiB

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 (stderr)

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 / 100