Submission #400051

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
400051	2021-05-07T09:06:26 Z	Joshc	Queue (CEOI06_queue)	C++11	100 / 100	283 ms	18048 KB

queue

#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define pii pair<int, int>
#define f first
#define s second

map<int, int> before, after;
map<int, pii> pos;

int prv(int x) {
    return before.find(x) != before.end() ? before[x] : x-1;
}

int nxt(int x) {
    return after.find(x) != after.end() ? after[x] : x+1;
}

int main() {
    int n, a, b, cur=1, len=0;
    char c;
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d", &a, &b);
        if (b == cur) cur = a;
        else if (a == cur) cur = nxt(a);
        after[prv(a)] = nxt(a);
        before[nxt(a)] = prv(a);
        after[prv(b)] = a;
        before[a] = prv(b);
        after[a] = b;
        before[b] = a;
    }
    vector<pii> intervals;
    vector<int> lengths;
    while (true) {
        auto x = after.lower_bound(cur);
        if (x == after.end()) {
            intervals.emplace_back(cur, 1000000000);
            break;
        }
        intervals.emplace_back(cur, x->f);
        cur = x->s;
    }
    for (auto i : intervals) {
        lengths.push_back(len += i.s-i.f+1);
        pos[i.s] = {i.s, len};
    }
    scanf("%d", &n);
    while (n--) {
        scanf(" %c%d", &c, &a);
        if (c == 'P') {
            pii ans = (*pos.lower_bound(a)).s;
            printf("%d\n", ans.s-ans.f+a);
        } else {
            int ans = lower_bound(lengths.begin(), lengths.end(), a)-lengths.begin();
            printf("%d\n", intervals[ans].s-lengths[ans]+a);
        }
    }
}

Compilation message

queue.cpp: In function 'int main()':
queue.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
queue.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
queue.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
queue.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         scanf(" %c%d", &c, &a);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	2 ms	204 KB	Output is correct
4	Correct	3 ms	460 KB	Output is correct
5	Correct	24 ms	1248 KB	Output is correct
6	Correct	34 ms	2144 KB	Output is correct
7	Correct	46 ms	3084 KB	Output is correct
8	Correct	59 ms	4952 KB	Output is correct
9	Correct	67 ms	5540 KB	Output is correct
10	Correct	74 ms	5920 KB	Output is correct
11	Correct	201 ms	12796 KB	Output is correct
12	Correct	196 ms	10684 KB	Output is correct
13	Correct	209 ms	12856 KB	Output is correct
14	Correct	221 ms	12852 KB	Output is correct
15	Correct	223 ms	12984 KB	Output is correct
16	Correct	210 ms	12984 KB	Output is correct
17	Correct	31 ms	996 KB	Output is correct
18	Correct	55 ms	1148 KB	Output is correct
19	Correct	88 ms	2596 KB	Output is correct
20	Correct	145 ms	3960 KB	Output is correct
21	Correct	147 ms	12472 KB	Output is correct
22	Correct	210 ms	14844 KB	Output is correct
23	Correct	283 ms	17980 KB	Output is correct
24	Correct	275 ms	18048 KB	Output is correct
25	Correct	242 ms	14272 KB	Output is correct