답안 #1010866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010866	2024-06-29T12:55:59 Z	vjudge1	Queue (CEOI06_queue)	C++17	96 / 100	325 ms	29136 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});

    while (n--) {
        int a, b;
        cin >> a >> b;

        auto ind = st.upper_bound({a, 2 * inf});
        ind--;
        auto cur = *ind;
        if (a >= cur[0] && 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 (a >= cur[0] && 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[a]) {
            Prv[a] = a - 1;
            Nxt[a - 1] = a;
        }
        if (!Prv[b]) {
            Prv[b] = b - 1;
            Nxt[b - 1] = b;
        }
        if (!Nxt[a]) {
            Nxt[a] = a + 1;
            Prv[a + 1] = a;
        }
        if (!Nxt[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));

    if (!Nxt[0]) {
        Nxt[0] = 1;
    }
    if (!Nxt[inf]) {
        Nxt[inf] = inf + 1;
    }

    map<int, int> Ansv, Ansp;
    map<int, int> done;
    int cur_val = 0, cur_ind = 0;
    while (cur_val <= inf) {
        done[cur_val] = 1;
        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:112:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while (idx < Val.size() && Val[idx] <= rv) {
      |                    ~~~~^~~~~~~~~~~~
queue.cpp:118:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |             while (idx < Pos.size() && Pos[idx] <= rp) {
      |                    ~~~~^~~~~~~~~~~~
queue.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |         while (idx < Val.size() && Val[idx] <= rv) {
      |                ~~~~^~~~~~~~~~~~
queue.cpp:138:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         while (idx < Pos.size() && Pos[idx] <= rp) {
      |                ~~~~^~~~~~~~~~~~

Subtask #1

96.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 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	37 ms	5000 KB	Output is correct
6	Correct	47 ms	6620 KB	Output is correct
7	Correct	59 ms	7524 KB	Output is correct
8	Correct	77 ms	10708 KB	Output is correct
9	Correct	88 ms	11088 KB	Output is correct
10	Correct	87 ms	11600 KB	Output is correct
11	Correct	198 ms	17580 KB	Output is correct
12	Correct	179 ms	12424 KB	Output is correct
13	Correct	212 ms	18000 KB	Output is correct
14	Correct	197 ms	18256 KB	Output is correct
15	Correct	212 ms	18516 KB	Output is correct
16	Correct	225 ms	18388 KB	Output is correct
17	Correct	24 ms	2384 KB	Output is correct
18	Correct	45 ms	3920 KB	Output is correct
19	Correct	64 ms	4080 KB	Output is correct
20	Correct	116 ms	7252 KB	Output is correct
21	Incorrect	166 ms	18540 KB	Output isn't correct
22	Correct	240 ms	23468 KB	Output is correct
23	Correct	318 ms	29136 KB	Output is correct
24	Correct	325 ms	29008 KB	Output is correct
25	Correct	236 ms	19812 KB	Output is correct