Submission #400016

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
400016	2021-05-07T06:27:40 Z	Joshc	Queue (CEOI06_queue)	C++11	56 / 100	629 ms	65540 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;
        int pa = prv(a), na = nxt(a), pb = prv(b);
        after[pa] = na;
        before[na] = pa;
        after[pb] = a;
        before[a] = pb;
        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

56.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Runtime error	92 ms	65540 KB	Execution killed with signal 9
3	Runtime error	108 ms	65540 KB	Execution killed with signal 9
4	Correct	3 ms	564 KB	Output is correct
5	Correct	25 ms	1868 KB	Output is correct
6	Correct	34 ms	2788 KB	Output is correct
7	Correct	48 ms	3780 KB	Output is correct
8	Correct	57 ms	5740 KB	Output is correct
9	Correct	64 ms	6156 KB	Output is correct
10	Correct	72 ms	6688 KB	Output is correct
11	Correct	191 ms	13740 KB	Output is correct
12	Correct	168 ms	11196 KB	Output is correct
13	Correct	191 ms	13936 KB	Output is correct
14	Incorrect	167 ms	10048 KB	Output isn't correct
15	Incorrect	170 ms	11012 KB	Output isn't correct
16	Correct	198 ms	14088 KB	Output is correct
17	Runtime error	126 ms	65540 KB	Execution killed with signal 9
18	Incorrect	45 ms	1732 KB	Output isn't correct
19	Runtime error	373 ms	65540 KB	Execution killed with signal 9
20	Runtime error	629 ms	65540 KB	Execution killed with signal 9
21	Incorrect	123 ms	12084 KB	Output isn't correct
22	Correct	189 ms	16068 KB	Output is correct
23	Correct	260 ms	19516 KB	Output is correct
24	Incorrect	227 ms	16816 KB	Output isn't correct
25	Incorrect	230 ms	15808 KB	Output isn't correct