oj.uz

답안 #752792

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752792 2023-06-03T20:59:59 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 354 ms 34220 KB 
#include <bits/stdc++.h>
using namespace std;
int n, q, arr[202020];
 
int ans[1010101];
int res[202020];
int nxt[202020];
stack< pair<int, int> > S;
 
int qnum = 0;
struct query {
    int time, idx, ord;
    bool operator<(const query &other) const {
        if (time == other.time) return idx < other.idx;
        return time > other.time;
    }
} queries[1010101];
 
struct segment {
    int first, st, ed, sz;
    bool operator<(const segment &other) const {
        return first > other.first;
    }
};
set<segment> segs;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];
 
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].time >> queries[i].idx;
        queries[i].ord = i;
    }
    sort(queries + 1, queries + q + 1);
 
    while (1) {
        if (queries[qnum].time > 0) break;
        ans[queries[qnum].ord] = arr[queries[qnum].idx];
        qnum++;
    }

    for (int i = 1; i <= n; i++) {
        while (!S.empty()) {
            if (S.top().second < arr[i]) {
                nxt[S.top().first] = i;
                S.pop();
            }
            else break;
        }
        S.push({i, arr[i]});
    }
    while (!S.empty()) {
        nxt[S.top().first] = n + 1;
        S.pop();
    }
 
    int k = 1;
    while (nxt[k] <= n/2) {
        segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
        k = nxt[k];
    }
    segs.insert({arr[k], k, n/2, n/2 - k + 1});
 
    k = n/2 + 1;
    while (nxt[k] <= n) {
        segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
        k = nxt[k];
    }
    segs.insert({arr[k], k, n, n - k + 1});
 
    int cnt = 0, p = n;
    for (int t = 1; t < queries[q].time; t++) {
        while (1) {
            assert(segs.size() > 0);
            if (cnt + segs.begin()->sz > n/2) break;
            cnt += segs.begin()->sz;
            for (int i = segs.begin()->ed; i >= segs.begin()->st; i--) {
                assert(p >= 1);
                res[p--] = arr[i];
            }
            segs.erase(segs.begin());
        }
        if (cnt == n/2) break;
        segment div = *segs.begin();
        segs.erase(segs.begin());
        segs.insert({div.first, div.st, div.st + cnt + div.sz - n/2 - 1, cnt + div.sz - n/2});
        k = div.st + cnt + div.sz - n/2;
        while (nxt[k] <= div.ed) {
            segs.insert({arr[k], k, nxt[k] - 1, nxt[k] - k});
            k = nxt[k];
        }
        segs.insert({arr[k], k, div.ed, div.ed - k + 1});
    }
 

    for (set<segment>::iterator iter = segs.begin(); iter != segs.end(); iter++) {
        for (int i = iter->ed; i >= iter->st; i--) {
            res[p--] = arr[i];
        }
    }
    for (int i = 1; i <= q; i++) {
        ans[queries[i].ord] = res[queries[i].idx];
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
 
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 287 ms 19936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 28260 KB Output is correct
2 Correct 354 ms 34220 KB Output is correct
3 Correct 295 ms 25828 KB Output is correct
4 Correct 268 ms 22188 KB Output is correct
5 Correct 306 ms 23592 KB Output is correct
6 Correct 247 ms 21172 KB Output is correct
7 Correct 315 ms 26188 KB Output is correct
8 Correct 335 ms 25440 KB Output is correct
9 Correct 294 ms 22952 KB Output is correct
10 Correct 300 ms 23904 KB Output is correct
11 Correct 267 ms 20176 KB Output is correct
12 Correct 240 ms 19896 KB Output is correct
13 Correct 353 ms 23904 KB Output is correct
14 Correct 255 ms 20624 KB Output is correct
15 Correct 301 ms 24448 KB Output is correct
16 Correct 20 ms 2644 KB Output is correct
17 Runtime error 183 ms 32412 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 4020 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 287 ms 19936 KB Output isn't correct
2 Halted 0 ms 0 KB -