oj.uz

답안 #400051

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400051 2021-05-07T09:06:26 Z Joshc Queue (CEOI06_queue) C++11
100 / 100
 283 ms 18048 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;
        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

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