답안 #1010897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010897	2024-06-29T13:54:50 Z	Essa2006	Queue (CEOI06_queue)	C++14	100 / 100	265 ms	18772 KB

queue

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)

const int inf = 1e9;

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin >> n;
    map<int, int> Nxt, Prv;
    set<array<int, 2>> st;
    st.insert({0, inf + 1});
    Nxt[1e9] = 1e9 + 1;
    Prv[1e9 + 1] = 1e9;
    Prv[1] = 0;
    Nxt[0] = 1;
    while (n--) {
        int a, b;
        cin >> a >> b;

        auto ind = st.upper_bound({a, 2 * inf});
        ind--;
        auto cur = *ind;
        if (cur[0] <= a && a <= cur[1]) {
            st.erase(ind);
            if (a - 1 >= cur[0]) {
                st.insert({cur[0], a - 1});
            }
            if (a + 1 <= cur[1]) {
                st.insert({a + 1, cur[1]});
            }
        }

        swap(a, b);
        ind = st.upper_bound({a, 2 * inf});
        ind--;
        cur = *ind;
        if (cur[0] <= a && a <= cur[1]) {
            st.erase(ind);
            if (a - 1 >= cur[0]) {
                st.insert({cur[0], a - 1});
            }
            if (a + 1 <= cur[1]) {
                st.insert({a + 1, cur[1]});
            }
        }
        swap(a, b);

        if (!Prv.count(a)) {
            Prv[a] = a - 1;
            Nxt[a - 1] = a;
        }
        if (!Prv.count(b)) {
            Prv[b] = b - 1;
            Nxt[b - 1] = b;
        }
        if (!Nxt.count(a)) {
            Nxt[a] = a + 1;
            Prv[a + 1] = a;
        }
        if (!Nxt.count(b)) {
            Nxt[b] = b + 1;
            Prv[b + 1] = b;
        }
        Nxt[Prv[a]] = Nxt[a], Prv[Nxt[a]] = Prv[a];
        Nxt[Prv[b]] = a, Prv[a] = Prv[b];
        Nxt[a] = b, Prv[b] = a;
    }

    vector<int> Pos, Val;
    int q;
    cin >> q;
    vector<array<int, 2>> Q(q);
    for (int i = 0; i < q; i++) {
        char kind;
        int cur;
        cin >> kind >> cur;
        if (kind == 'P') {
            Q[i][0] = 0;
            Val.push_back(cur);
        }
        else {
            Q[i][0] = 1;
            Pos.push_back(cur);
        }
        Q[i][1] = cur;
    }

    sort(all(Pos));
    sort(all(Val));

    map<int, int> Ansv, Ansp;
    int cur_val = 0, cur_ind = 0;
    while (cur_val <= inf) {
        if (Nxt.count(cur_val)) {
            int lv = cur_val, rv = cur_val;
            int idx = lower_bound(all(Val), lv) - Val.begin();
            while (idx < Val.size() && Val[idx] <= rv) {
                Ansp[Val[idx]] = cur_ind;
                idx++;
            }
            int lp = cur_ind, rp = cur_ind;
            idx = lower_bound(all(Pos), lp) - Pos.begin();
            while (idx < Pos.size() && Pos[idx] <= rp) {
                Ansv[Pos[idx]] = cur_val;
                idx++;
            }
            cur_val = Nxt[cur_val];
            cur_ind++;
            continue;
        }
        auto ind = st.upper_bound({cur_val,  2 * inf});
        ind--;
        auto cur = *ind;
        int diff = cur[1] - cur_val;
        int lv = cur_val, rv = cur_val + diff - 1;
        int idx = lower_bound(all(Val), lv) - Val.begin();
        while (idx < Val.size() && Val[idx] <= rv) {
            Ansp[Val[idx]] = cur_ind + (Val[idx] - lv);
            idx++;
        }
        int lp = cur_ind, rp = cur_ind + diff - 1;
        idx = lower_bound(all(Pos), lp) - Pos.begin();
        while (idx < Pos.size() && Pos[idx] <= rp) {
            Ansv[Pos[idx]] = cur_val + (Pos[idx] - lp);
            idx++;
        }
        cur_ind += cur[1] - cur_val;
        cur_val = cur[1];
    }

    for (int i = 0; i < q; i++) {
        if (!Q[i][0]) {
            cout << Ansp[Q[i][1]] << endl;
        }
        else {
            cout << Ansv[Q[i][1]] << endl;
        }
    }
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:107:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             while (idx < Val.size() && Val[idx] <= rv) {
      |                    ~~~~^~~~~~~~~~~~
queue.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             while (idx < Pos.size() && Pos[idx] <= rp) {
      |                    ~~~~^~~~~~~~~~~~
queue.cpp:127:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |         while (idx < Val.size() && Val[idx] <= rv) {
      |                ~~~~^~~~~~~~~~~~
queue.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |         while (idx < Pos.size() && Pos[idx] <= rp) {
      |                ~~~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	34 ms	4308 KB	Output is correct
6	Correct	39 ms	5080 KB	Output is correct
7	Correct	51 ms	5816 KB	Output is correct
8	Correct	65 ms	7636 KB	Output is correct
9	Correct	74 ms	7764 KB	Output is correct
10	Correct	81 ms	8056 KB	Output is correct
11	Correct	174 ms	10580 KB	Output is correct
12	Correct	169 ms	8016 KB	Output is correct
13	Correct	177 ms	10832 KB	Output is correct
14	Correct	182 ms	11092 KB	Output is correct
15	Correct	229 ms	11348 KB	Output is correct
16	Correct	190 ms	11408 KB	Output is correct
17	Correct	23 ms	1620 KB	Output is correct
18	Correct	43 ms	2904 KB	Output is correct
19	Correct	66 ms	2644 KB	Output is correct
20	Correct	115 ms	4880 KB	Output is correct
21	Correct	149 ms	13040 KB	Output is correct
22	Correct	191 ms	15268 KB	Output is correct
23	Correct	265 ms	18576 KB	Output is correct
24	Correct	223 ms	18772 KB	Output is correct
25	Correct	211 ms	13260 KB	Output is correct