oj.uz

Submission #752797

# Submission time Handle Problem Language Result Execution time Memory
752797 2023-06-03T21:06:50 Z math_rabbit_1028 Abracadabra (CEOI22_abracadabra) C++14
40 / 100
 333 ms 35084 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;
        queries[i].time = min(queries[i].time, n);
    }
    sort(queries + 1, queries + q + 1);
 
    while (qnum <= q) {
        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++) {
        if (queries[qnum].time == t) {
            for (set<segment>::iterator iter = segs.begin(); iter != segs.end(); iter++) {
                for (int i = iter->ed; i >= iter->st; i--) {
                    res[p--] = arr[i];
                }
            }
        }
 
        while (qnum <= q) {
            if (queries[qnum].time != t) break;
            ans[queries[qnum].ord] = res[queries[qnum].idx];
            qnum++;
        }
        while (1) {
            if (cnt + segs.begin()->sz > n/2) break;
            cnt += segs.begin()->sz;
            for (int i = segs.begin()->ed; i >= segs.begin()->st; i--) {
                res[p--] = arr[i];
            }
            segs.erase(segs.begin());
        }
        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 (int i = 1; i <= q; i++) cout << ans[i] << "\n";
 
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 14040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 28220 KB Output is correct
2 Correct 333 ms 34192 KB Output is correct
3 Correct 277 ms 25884 KB Output is correct
4 Correct 266 ms 22168 KB Output is correct
5 Correct 292 ms 23540 KB Output is correct
6 Correct 262 ms 21116 KB Output is correct
7 Correct 331 ms 26104 KB Output is correct
8 Correct 306 ms 25412 KB Output is correct
9 Correct 262 ms 22856 KB Output is correct
10 Correct 302 ms 23904 KB Output is correct
11 Correct 305 ms 20336 KB Output is correct
12 Correct 250 ms 20012 KB Output is correct
13 Correct 315 ms 24016 KB Output is correct
14 Correct 253 ms 20428 KB Output is correct
15 Correct 292 ms 24440 KB Output is correct
16 Correct 18 ms 2636 KB Output is correct
17 Correct 308 ms 35084 KB Output is correct
18 Correct 215 ms 21200 KB Output is correct
19 Correct 78 ms 6128 KB Output is correct
20 Correct 88 ms 7116 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 2840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 14040 KB Output isn't correct
2 Halted 0 ms 0 KB -