답안 #138791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
138791 2019-07-30T10:29:58 Z popovicirobert Queue (CEOI06_queue) C++14
100 / 100
258 ms 15620 KB
#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]) {
                ~~^~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 6 ms 2936 KB Output is correct
5 Correct 36 ms 5112 KB Output is correct
6 Correct 52 ms 6776 KB Output is correct
7 Correct 51 ms 6260 KB Output is correct
8 Correct 55 ms 6768 KB Output is correct
9 Correct 68 ms 7668 KB Output is correct
10 Correct 73 ms 7924 KB Output is correct
11 Correct 139 ms 9936 KB Output is correct
12 Correct 141 ms 10020 KB Output is correct
13 Correct 142 ms 9964 KB Output is correct
14 Correct 147 ms 10016 KB Output is correct
15 Correct 155 ms 10008 KB Output is correct
16 Correct 143 ms 10476 KB Output is correct
17 Correct 22 ms 3324 KB Output is correct
18 Correct 34 ms 3784 KB Output is correct
19 Correct 55 ms 4984 KB Output is correct
20 Correct 76 ms 4940 KB Output is correct
21 Correct 120 ms 10844 KB Output is correct
22 Correct 162 ms 13032 KB Output is correct
23 Correct 212 ms 15516 KB Output is correct
24 Correct 214 ms 15620 KB Output is correct
25 Correct 258 ms 14312 KB Output is correct