Submission #136225

#	Time	Username	Problem	Language	Result	Execution time	Memory
136225		imeimi2000	Queue (CEOI06_queue)	C++17	100 / 100	232 ms	15464 KiB

queue

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

struct node {
    int x, prv, nxt;
    node() : x(0), prv(0), nxt(0) {}
    node(int x) : x(x), prv(0), nxt(0) {}
} ns[200001];
int tp = 0;

map<int, int> first;
map<int, int> group;
map<int, int> nodei;

void make_label(int x) {
    if (nodei.count(x)) return;
    int ni = ++tp;
    ns[ni] = node(x);
    nodei[x] = ni;
    group[x] = x;
    ns[first[x] = ++tp] = node();
    ns[tp].nxt = ni;
    ns[ni].prv = tp;
}

const int inf = 1e9;
bool T[50001];
int X[50001];
int ans[50001];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        make_label(a);
        make_label(b);
        int ai = nodei[a], bi = nodei[b];
        if (ns[ai].prv) ns[ns[ai].prv].nxt = ns[ai].nxt;
        if (ns[ai].nxt) ns[ns[ai].nxt].prv = ns[ai].prv;
        ns[ai].prv = ns[ai].nxt = 0;
        ns[ai].nxt = bi;
        ns[ai].prv = ns[bi].prv;
        if (ns[bi].prv) ns[ns[bi].prv].nxt = ai;
        ns[bi].prv = ai;
    }
    vector<pii> ord;
    int pri = 0;
    for (auto it : first) {
        int i = it.first;
        int x = it.second;
        if (pri + 1 <= i - 1) ord.emplace_back(pri + 1, i - 1);
        pri = i;
        for (x = ns[x].nxt; x; x = ns[x].nxt)
            ord.emplace_back(ns[x].x, ns[x].x);
    }
    if (pri + 1 <= inf) ord.emplace_back(pri + 1, inf);
    int q;
    cin >> q;
    vector<int> ql;
    set<pii> qp;
    for (int i = 1; i <= q; ++i) {
        char in[10];
        cin >> in >> X[i];
        T[i] = in[0] == 'L';
        if (T[i]) ql.push_back(i);
        else qp.emplace(X[i], i);
    }
    sort(ql.begin(), ql.end(), [&](int a, int b) {
        return X[a] < X[b];
    });
    int sum = 0, j = 0;
    for (int i : ql) {
        while (j < ord.size() && sum + ord[j].second - ord[j].first + 1 < X[i]) {
            sum += ord[j].second - ord[j].first + 1;
            ++j;
        }
        ans[i] = X[i] - sum + ord[j].first - 1;
    }
    sum = 0;
    for (pii i : ord) {
        while (1) {
            auto it = qp.lower_bound(pii(i.first, 0));
            if (it == qp.end() || i.second < it->first)
                break;
            ans[it->second] = sum + it->first - i.first + 1;
            qp.erase(it);
        }
        sum += i.second - i.first + 1;
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
    return 0;
}

Compilation message (stderr)

queue.cpp: In function 'int main()':
queue.cpp:83:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (j < ord.size() && sum + ord[j].second - ord[j].first + 1 < X[i]) {
                ~~^~~~~~~~~~~~

• Subtask 1: 100 / 100