Submission #1261423

#TimeUsernameProblemLanguageResultExecution timeMemory
1261423LithaniumQueue (CEOI06_queue)C++20
72 / 100
124 ms12344 KiB
#include <bits/stdc++.h> using namespace std; struct Node { int val; int l, r; int x; } nodes[400005]; int dt[50005][2]; int q[50005][2]; map<int, int> ans, pos; int N, Q; int main() { vector<int> cc, ask; cin >> N; for (int i = 1; i <= N; i ++) { cin >> 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]) cc.push_back(q[i][1]); else 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[(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]; } for (int i = 1; i <= Q; i ++) { if (q[i][0]) { cout << ans[q[i][1]] << "\n"; } else { cout << pos[q[i][1]] << "\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...