Submission #1261429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261429		Lithanium	Queue (CEOI06_queue)	C++20	100 / 100	61 ms	11300 KiB

queue

#pragma GCC optimize("Ofast,unroll-loops")

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    int l, r;
    int x;
} nodes[300005];

int dt[50005][2];
int q[50005][2];
unordered_map<int, int> ans, pos;
int N, Q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<int> cc, ask;
    cin >> N;
    for (int i = 1; i <= N; i ++) {
        cin >> dt[i][0] >> dt[i][1];
        dt[i][0] ++, dt[i][1] ++;
        cc.push_back(dt[i][0]);
        cc.push_back(dt[i][1]);
    }
    cin >> Q;
    for (int i = 1; i <= Q; i ++) {
        char c;
        cin >> c;
        q[i][0] = (c == 'L');
        cin >> q[i][1];
        if (!q[i][0]) {
            q[i][1] ++;
            cc.push_back(q[i][1]);
        } else {
            // q[i][1] ++;
            ask.push_back(q[i][1]);
        }
    }
    cc.push_back(1);
    cc.push_back(1e9+5);
    sort(cc.begin(), cc.end());
    cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
    for (int i = 0; i < cc.size()-1; i ++) {
        int l = cc[i], r = cc[i+1];
        int sz = r - l - 1;
        if (sz) {
            // create a new one
            nodes[2*i].r = nodes[2*i+2].l = 2*i+1;
            nodes[2*i+1].l = 2*i;
            nodes[2*i+1].r = 2*i+2;
            nodes[2*i+1].val = sz;
            nodes[2*i+1].x = r-1;
            nodes[2*i].x = l, nodes[2*i+2].x = r;
            nodes[2*i].val = nodes[2*i+2].val = 1;
        } else {
            nodes[2*i].val = nodes[2*i+2].val = 1;
            nodes[2*i].x = l, nodes[2*i+2].x = r;
            nodes[2*i].r = 2*i+2;
            nodes[2*i+2].l = 2*i;
        }
    }
    nodes[0].val = 0;
    nodes[(cc.size()-1)*2].r = -1;
    int HEAD = 2*cc.size();
    nodes[HEAD].val = 0;
    nodes[HEAD].r = 0;
    for (int i = 1; i <= N; i ++) {
        // move dt[i][0] out of the way
        int t = lower_bound(cc.begin(), cc.end(), dt[i][0]) - cc.begin();
        int l = nodes[2*t].l, r = nodes[2*t].r;
        nodes[l].r = r;
        nodes[r].l = l;
        // move dt[i][0] in front of dt[i][1]
        int t2 = lower_bound(cc.begin(), cc.end(), dt[i][1]) - cc.begin();
        int temp = nodes[2*t2].l;
        nodes[temp].r = 2*t;
        nodes[2*t].l = temp;
        nodes[2*t].r = 2*t2;
        nodes[2*t2].l = 2*t;
    }
    Node curr = nodes[HEAD];
    sort(ask.begin(), ask.end());
    int ptr = 0, psa = 0;
    while (curr.r != -1) {
        psa += curr.val;
        while (ptr < ask.size() and ask[ptr] <= psa) {
            int diff = psa - ask[ptr];
            ans[ask[ptr]] = curr.x - diff;
            ptr ++;
        }
        pos[curr.x] = psa;
        curr = nodes[curr.r];
        // cout << curr.x << " -> ";
        // if (rand()%5) break;
    }
    for (int i = 1; i <= Q; i ++) {
        if (q[i][0]) {
            cout << ans[q[i][1]]-1 << "\n";
        } else {
            cout << pos[q[i][1]] << "\n";
        }
    }
}

• Subtask 1: 100 / 100