답안 #1010887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010887	2024-06-29T13:28:56 Z	vjudge1	Queue (CEOI06_queue)	C++17	96 / 100	265 ms	18640 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[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));

    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

96.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	480 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	32 ms	4180 KB	Output is correct
6	Correct	38 ms	5080 KB	Output is correct
7	Correct	50 ms	5712 KB	Output is correct
8	Correct	63 ms	7636 KB	Output is correct
9	Correct	66 ms	7656 KB	Output is correct
10	Correct	89 ms	7988 KB	Output is correct
11	Correct	166 ms	10580 KB	Output is correct
12	Correct	176 ms	8040 KB	Output is correct
13	Correct	197 ms	10832 KB	Output is correct
14	Correct	202 ms	11128 KB	Output is correct
15	Correct	192 ms	11344 KB	Output is correct
16	Correct	185 ms	11344 KB	Output is correct
17	Correct	24 ms	1628 KB	Output is correct
18	Correct	42 ms	2892 KB	Output is correct
19	Correct	66 ms	2628 KB	Output is correct
20	Correct	125 ms	4888 KB	Output is correct
21	Incorrect	140 ms	12844 KB	Output isn't correct
22	Correct	188 ms	15512 KB	Output is correct
23	Correct	254 ms	18640 KB	Output is correct
24	Correct	265 ms	18624 KB	Output is correct
25	Correct	206 ms	13260 KB	Output is correct