답안 #1010883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010883	2024-06-29T13:11:30 Z	Essa2006	Queue (CEOI06_queue)	C++14	96 / 100	362 ms	18708 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});
    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:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |             while (idx < Val.size() && Val[idx] <= rv) {
      |                    ~~~~^~~~~~~~~~~~
queue.cpp:111:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |             while (idx < Pos.size() && Pos[idx] <= rp) {
      |                    ~~~~^~~~~~~~~~~~
queue.cpp:125:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         while (idx < Val.size() && Val[idx] <= rv) {
      |                ~~~~^~~~~~~~~~~~
queue.cpp:131:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         while (idx < Pos.size() && Pos[idx] <= rp) {
      |                ~~~~^~~~~~~~~~~~

Subtask #1

96.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	352 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	3 ms	604 KB	Output is correct
5	Correct	29 ms	4364 KB	Output is correct
6	Correct	48 ms	5120 KB	Output is correct
7	Correct	52 ms	5712 KB	Output is correct
8	Correct	69 ms	7624 KB	Output is correct
9	Correct	102 ms	7616 KB	Output is correct
10	Correct	87 ms	8016 KB	Output is correct
11	Correct	209 ms	10560 KB	Output is correct
12	Correct	166 ms	8096 KB	Output is correct
13	Correct	218 ms	10904 KB	Output is correct
14	Correct	189 ms	11088 KB	Output is correct
15	Correct	193 ms	11208 KB	Output is correct
16	Correct	211 ms	11344 KB	Output is correct
17	Correct	25 ms	1628 KB	Output is correct
18	Correct	43 ms	2896 KB	Output is correct
19	Correct	64 ms	2640 KB	Output is correct
20	Correct	139 ms	4880 KB	Output is correct
21	Incorrect	182 ms	12880 KB	Output isn't correct
22	Correct	350 ms	15280 KB	Output is correct
23	Correct	354 ms	18708 KB	Output is correct
24	Correct	362 ms	18540 KB	Output is correct
25	Correct	301 ms	13424 KB	Output is correct