Submission #136225

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136225	2019-07-25T04:14:14 Z	imeimi2000	Queue (CEOI06_queue)	C++17	100 / 100	232 ms	15464 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	4 ms	2700 KB	Output is correct
3	Correct	6 ms	2808 KB	Output is correct
4	Correct	6 ms	2936 KB	Output is correct
5	Correct	37 ms	5096 KB	Output is correct
6	Correct	53 ms	6748 KB	Output is correct
7	Correct	52 ms	6260 KB	Output is correct
8	Correct	57 ms	6636 KB	Output is correct
9	Correct	70 ms	7668 KB	Output is correct
10	Correct	73 ms	7924 KB	Output is correct
11	Correct	127 ms	9972 KB	Output is correct
12	Correct	127 ms	9948 KB	Output is correct
13	Correct	183 ms	10096 KB	Output is correct
14	Correct	166 ms	10020 KB	Output is correct
15	Correct	151 ms	9972 KB	Output is correct
16	Correct	174 ms	10264 KB	Output is correct
17	Correct	22 ms	3320 KB	Output is correct
18	Correct	33 ms	3832 KB	Output is correct
19	Correct	56 ms	4948 KB	Output is correct
20	Correct	80 ms	4852 KB	Output is correct
21	Correct	123 ms	10736 KB	Output is correct
22	Correct	180 ms	13132 KB	Output is correct
23	Correct	232 ms	15464 KB	Output is correct
24	Correct	221 ms	15084 KB	Output is correct
25	Correct	207 ms	14284 KB	Output is correct