Submission #1219355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219355		dizzy_groovy	Queue (CEOI06_queue)	C++20	100 / 100	103 ms	4024 KiB

queue

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> v(n);
    vector<int> x(1, 0);
    for (auto &i : v) {
        cin >> i.first >> i.second;
        x.push_back(i.first);
        x.push_back(i.first + 1);
        x.push_back(i.second);
    }
    sort(x.begin(), x.end());
    x.resize(unique(x.begin(), x.end()) - x.begin());
    for (auto &i : v) {
        i.first = lower_bound(x.begin(), x.end(), i.first) - x.begin();
        i.second = lower_bound(x.begin(), x.end(), i.second) - x.begin();
    }
    vector<int> prv(x.size());
    vector<int> nxt(x.size());
    for (int i = 0; i < x.size(); i++) {
        prv[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[x.size() - 1] = -1;
    for (auto &i : v) {
        if (nxt[i.first] != -1) {
            prv[nxt[i.first]] = prv[i.first];
        }
        if (prv[i.first] != -1) {
            nxt[prv[i.first]] = nxt[i.first];
        }
        prv[i.first] = prv[i.second];
        nxt[i.first] = i.second;
        prv[i.second] = i.first;
        if (prv[i.first] != -1) {
            nxt[prv[i.first]] = i.first;
        }
    }
    vector<pair<int, int>> curv;
    vector<int> ind(x.size());
    x.push_back(1e9 + 52);
    int su = 0;
    for (int i = 0; i != -1; i = nxt[i]) {
        su += x[i + 1] - x[i];
        ind[i] = curv.size();
        curv.push_back({su, i});
    }
    int q;
    cin >> q;
    while (q--) {
        char t;
        int curx;
        cin >> t >> curx;
        if (t == 'L') {
            //curx--;
            int ind1 = upper_bound(curv.begin(), curv.end(), make_pair(curx, (int)1e9)) - curv.begin();
            int p = 0;
            if (ind1 > 0) p = curv[ind1 - 1].first;
            cout << x[curv[ind1].second] + (curx - p) << "\n";
        } else {
            int ind1 = prev(upper_bound(x.begin(), x.end(), curx)) - x.begin();
            int ind2 = ind[ind1];
            int p = 0;
            if (ind2 > 0) p += curv[ind2 - 1].first;
            cout << p + (curx - x[ind1]) << "\n";
        }
    }
}

• Subtask 1: 100 / 100