답안 #1010898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010898	2024-06-29T13:55:14 Z	vjudge1	Queue (CEOI06_queue)	C++17	100 / 100	260 ms	18924 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	2 ms	604 KB	Output is correct
5	Correct	27 ms	4288 KB	Output is correct
6	Correct	38 ms	5092 KB	Output is correct
7	Correct	54 ms	5788 KB	Output is correct
8	Correct	66 ms	7688 KB	Output is correct
9	Correct	72 ms	7764 KB	Output is correct
10	Correct	78 ms	8204 KB	Output is correct
11	Correct	175 ms	10476 KB	Output is correct
12	Correct	161 ms	7924 KB	Output is correct
13	Correct	160 ms	10840 KB	Output is correct
14	Correct	165 ms	11212 KB	Output is correct
15	Correct	189 ms	11120 KB	Output is correct
16	Correct	188 ms	11188 KB	Output is correct
17	Correct	23 ms	1880 KB	Output is correct
18	Correct	43 ms	2900 KB	Output is correct
19	Correct	65 ms	2680 KB	Output is correct
20	Correct	117 ms	4884 KB	Output is correct
21	Correct	147 ms	13136 KB	Output is correct
22	Correct	197 ms	15188 KB	Output is correct
23	Correct	260 ms	18924 KB	Output is correct
24	Correct	255 ms	18756 KB	Output is correct
25	Correct	230 ms	13420 KB	Output is correct