답안 #138791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
138791	2019-07-30T10:29:58 Z	popovicirobert	Queue (CEOI06_queue)	C++14	100 / 100	258 ms	15620 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

#	결과	실행 시간	메모리	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