Submission #400016

#	Time	Username	Problem	Language	Result	Execution time	Memory
400016		Joshc	Queue (CEOI06_queue)	C++11	56 / 100	629 ms	65540 KiB

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 (stderr)

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 / 100