oj.uz

답안 #400016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400016 2021-05-07T06:27:40 Z Joshc Queue (CEOI06_queue) C++11
56 / 100
 629 ms 65540 KB 
#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

# 결과 실행 시간 메모리 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