oj.uz

Submission #861205

# Submission time Handle Problem Language Result Execution time Memory
861205 2023-10-15T16:19:16 Z vgtcross Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 618 ms 58368 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct segtree {
    int v;
    int l, r, m;
    segtree *lc = nullptr, *rc = nullptr;
    
    segtree(int L, int R, vector<int> &u) {
        l = L;
        r = R;
        m = (l + r) / 2;
        if (l == r) {
            v = u[m];
            return;
        }
        
        lc = new segtree(l, m, u);
        rc = new segtree(m+1, r, u);
        v = lc->v + rc->v;
    }
    
    void point_set(int i, int k) {
        if (l == i && i == r) {
            v = k;
            return;
        }
        if (i <= m) lc->point_set(i, k);
        else rc->point_set(i, k);
        v = lc->v + rc->v;
    }
    
    pii get_val(int i) {
        if (l == r) return {m, i};
        if (i < lc->v) return lc->get_val(i);
        else return rc->get_val(i - lc->v);
    }
    
    void del() {
        if (lc != nullptr) lc->del();
        if (rc != nullptr) rc->del();
        delete lc;
        delete rc;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n+1, n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
    vector<int> b(n+1);
    for (int i = 0; i <= n; ++i) b[a[i]] = i;
    
    vector<array<int, 3>> que(q);
    for (int i = 0; i < q; ++i) {
        cin >> que[i][0] >> que[i][1];
        que[i][2] = i;
    }
    
    vector<int> nx(n+1);
    stack<int> st;
    for (int i : a) {
        while (st.size() && i > st.top()) {
            nx[st.top()] = i;
            st.pop();
        }
        st.push(i);
    }
    while (st.size()) {
        nx[st.top()] = n;
        st.pop();
    }
    
    vector<int> len(n, 0);
    for (int i = a[0]; i < n; i = nx[i]) len[i] = b[nx[i]] - b[i];
    
    segtree seg(0, n-1, len);
    
    sort(que.begin(), que.end());
    vector<int> ans(q);
    
    int j = 0;
    for (int i = 0; true; ++i) {
        while (j < q && que[j][0] == i) {
            pii p = seg.get_val(que[j][1]-1);
            ans[que[j][2]] = a[b[p.first] + p.second];
            ++j;
        }
        
        pii p = seg.get_val(n / 2);
        if (p.second == 0) break;
        for (int k = a[b[p.first] + p.second]; b[k] < b[p.first] + len[p.first]; k = nx[k]) {
            len[k] = min(b[nx[k]], b[p.first] + len[p.first]) - b[k];
            seg.point_set(k, len[k]);
        }
        len[p.first] = p.second;
        seg.point_set(p.first, len[p.first]);
    }
    
    while (j < q) {
        pii p = seg.get_val(que[j][1]-1);
        ans[que[j][2]] = a[b[p.first] + p.second];
        ++j;
    }
    
    for (int i = 0; i < q; ++i) cout << ans[i]+1 << '\n';
    
    seg.del();
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 20052 KB Output is correct
2 Correct 311 ms 20136 KB Output is correct
3 Correct 312 ms 19396 KB Output is correct
4 Correct 292 ms 19028 KB Output is correct
5 Correct 326 ms 20076 KB Output is correct
6 Correct 280 ms 19068 KB Output is correct
7 Correct 298 ms 19844 KB Output is correct
8 Correct 284 ms 19280 KB Output is correct
9 Correct 286 ms 19028 KB Output is correct
10 Correct 294 ms 19520 KB Output is correct
11 Correct 293 ms 19284 KB Output is correct
12 Correct 287 ms 19168 KB Output is correct
13 Correct 294 ms 19536 KB Output is correct
14 Correct 308 ms 19748 KB Output is correct
15 Correct 305 ms 19928 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 280 ms 19368 KB Output is correct
18 Correct 288 ms 19284 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 44528 KB Output is correct
2 Correct 349 ms 58064 KB Output is correct
3 Correct 316 ms 49476 KB Output is correct
4 Correct 321 ms 49704 KB Output is correct
5 Correct 329 ms 50944 KB Output is correct
6 Correct 317 ms 49176 KB Output is correct
7 Correct 339 ms 57424 KB Output is correct
8 Correct 335 ms 55120 KB Output is correct
9 Correct 316 ms 50640 KB Output is correct
10 Correct 306 ms 54096 KB Output is correct
11 Correct 297 ms 48916 KB Output is correct
12 Correct 284 ms 48208 KB Output is correct
13 Correct 301 ms 53584 KB Output is correct
14 Correct 307 ms 49748 KB Output is correct
15 Correct 315 ms 55424 KB Output is correct
16 Correct 35 ms 23376 KB Output is correct
17 Correct 299 ms 51668 KB Output is correct
18 Correct 275 ms 46348 KB Output is correct
19 Correct 81 ms 28944 KB Output is correct
20 Correct 88 ms 29876 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 14420 KB Output is correct
2 Correct 79 ms 15192 KB Output is correct
3 Correct 69 ms 14784 KB Output is correct
4 Correct 52 ms 14676 KB Output is correct
5 Correct 71 ms 15184 KB Output is correct
6 Correct 54 ms 14584 KB Output is correct
7 Correct 62 ms 14996 KB Output is correct
8 Correct 62 ms 14420 KB Output is correct
9 Correct 73 ms 15168 KB Output is correct
10 Correct 47 ms 14420 KB Output is correct
11 Correct 50 ms 14732 KB Output is correct
12 Correct 47 ms 14292 KB Output is correct
13 Correct 49 ms 14416 KB Output is correct
14 Correct 50 ms 14920 KB Output is correct
15 Correct 52 ms 14624 KB Output is correct
16 Correct 17 ms 11868 KB Output is correct
17 Correct 46 ms 14164 KB Output is correct
18 Correct 43 ms 14244 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 20052 KB Output is correct
2 Correct 311 ms 20136 KB Output is correct
3 Correct 312 ms 19396 KB Output is correct
4 Correct 292 ms 19028 KB Output is correct
5 Correct 326 ms 20076 KB Output is correct
6 Correct 280 ms 19068 KB Output is correct
7 Correct 298 ms 19844 KB Output is correct
8 Correct 284 ms 19280 KB Output is correct
9 Correct 286 ms 19028 KB Output is correct
10 Correct 294 ms 19520 KB Output is correct
11 Correct 293 ms 19284 KB Output is correct
12 Correct 287 ms 19168 KB Output is correct
13 Correct 294 ms 19536 KB Output is correct
14 Correct 308 ms 19748 KB Output is correct
15 Correct 305 ms 19928 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 280 ms 19368 KB Output is correct
18 Correct 288 ms 19284 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 358 ms 44528 KB Output is correct
22 Correct 349 ms 58064 KB Output is correct
23 Correct 316 ms 49476 KB Output is correct
24 Correct 321 ms 49704 KB Output is correct
25 Correct 329 ms 50944 KB Output is correct
26 Correct 317 ms 49176 KB Output is correct
27 Correct 339 ms 57424 KB Output is correct
28 Correct 335 ms 55120 KB Output is correct
29 Correct 316 ms 50640 KB Output is correct
30 Correct 306 ms 54096 KB Output is correct
31 Correct 297 ms 48916 KB Output is correct
32 Correct 284 ms 48208 KB Output is correct
33 Correct 301 ms 53584 KB Output is correct
34 Correct 307 ms 49748 KB Output is correct
35 Correct 315 ms 55424 KB Output is correct
36 Correct 35 ms 23376 KB Output is correct
37 Correct 299 ms 51668 KB Output is correct
38 Correct 275 ms 46348 KB Output is correct
39 Correct 81 ms 28944 KB Output is correct
40 Correct 88 ms 29876 KB Output is correct
41 Correct 72 ms 14420 KB Output is correct
42 Correct 79 ms 15192 KB Output is correct
43 Correct 69 ms 14784 KB Output is correct
44 Correct 52 ms 14676 KB Output is correct
45 Correct 71 ms 15184 KB Output is correct
46 Correct 54 ms 14584 KB Output is correct
47 Correct 62 ms 14996 KB Output is correct
48 Correct 62 ms 14420 KB Output is correct
49 Correct 73 ms 15168 KB Output is correct
50 Correct 47 ms 14420 KB Output is correct
51 Correct 50 ms 14732 KB Output is correct
52 Correct 47 ms 14292 KB Output is correct
53 Correct 49 ms 14416 KB Output is correct
54 Correct 50 ms 14920 KB Output is correct
55 Correct 52 ms 14624 KB Output is correct
56 Correct 17 ms 11868 KB Output is correct
57 Correct 46 ms 14164 KB Output is correct
58 Correct 43 ms 14244 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 553 ms 58368 KB Output is correct
62 Correct 604 ms 57680 KB Output is correct
63 Correct 618 ms 55596 KB Output is correct
64 Correct 461 ms 55600 KB Output is correct
65 Correct 449 ms 57616 KB Output is correct
66 Correct 429 ms 55256 KB Output is correct
67 Correct 417 ms 57172 KB Output is correct
68 Correct 444 ms 54868 KB Output is correct
69 Correct 442 ms 55756 KB Output is correct
70 Correct 412 ms 54616 KB Output is correct
71 Correct 386 ms 54352 KB Output is correct
72 Correct 374 ms 54112 KB Output is correct
73 Correct 383 ms 54340 KB Output is correct
74 Correct 387 ms 55744 KB Output is correct
75 Correct 382 ms 55732 KB Output is correct
76 Correct 34 ms 23380 KB Output is correct
77 Correct 362 ms 52044 KB Output is correct
78 Correct 380 ms 51796 KB Output is correct
79 Correct 0 ms 348 KB Output is correct
80 Correct 0 ms 348 KB Output is correct