oj.uz

Submission #653832

# Submission time Handle Problem Language Result Execution time Memory
653832 2022-10-28T12:03:35 Z Vladth11 Abracadabra (CEOI22_abracadabra) C++11
100 / 100
 1237 ms 110816 KB 
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>

#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

#pragma GCC optimize("Ofast")

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

const int bSize = 11;
const int bits = 17;
const int NMAX = 200001;
const int LIMIT = NMAX * bits;

vector <pii> qq[LIMIT + 1];
int sol[NMAX * 5];
int v[NMAX];
int poz[NMAX];
int stiva[NMAX];
int vf;
int nxt[NMAX];
pii interval[NMAX];
int aib[NMAX];

void update(int node, int x) {
    for(; node < NMAX; node += node&(-node))
        aib[node] += x;
}

int query(int node) {
    int x = 0;
    for(; node > 0; node -= node&(-node))
        x += aib[node];
    return x;
}

int cb(int k) {
    int r = 0, pas = (1 << bits), sum = 0;
    while(pas) {
        if(r + pas < NMAX && query(r + pas) < k) {
            r += pas;
        }
        pas /= 2;
    }
    r++;
    return r;
}

int sz(pii x) {
    if(x.second == 0)
        return 0;
    return x.second - x.first + 1;
}

int n;

void mShuffle() {
    int cine = cb(n / 2);
    if(query(cine) == n / 2) {
        return;
    }
    int dr = interval[cine].second;
    update(cine, -sz(interval[cine]));
    int pana = query(cine - 1);
    int node = n / 2;
    node -= pana;
    interval[cine] = {poz[cine], poz[cine] + node - 1};
    update(cine, sz(interval[cine]));
    int i = v[poz[cine] + node];
    while(sz(interval[i]) == 0 && poz[i] <= dr) {
        int urm = nxt[poz[i]];
        if(urm == 0)
            urm = n + 1;
        urm = min(urm, dr + 1);
        interval[i] = {poz[i], urm - 1};
        update(i, sz(interval[i]));
        if(urm != n + 1)
            i = v[urm];
        else
            break;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int q, i;
    cin >> n >> q;
    for(i = 1; i <= n; i++) {
        cin >> v[i];
        poz[v[i]] = i;
        while(vf && v[stiva[vf]] < v[i]) {
            nxt[stiva[vf]] = i;
            vf--;
        }
        stiva[++vf] = i;
    }
    i = 1;
    while(nxt[i] != 0) {
        interval[v[i]] = {i, nxt[i] - 1};
        i = nxt[i];
    }
    interval[v[i]] = {i, n};
    for(i = 1; i <= n; i++) {
        update(i, sz(interval[i]));
    }
    for(i = 1; i <= q; i++) {
        int x, y;
        cin >> x >> y;
        x = min(x, LIMIT);
        qq[x].push_back({y, i});
    }
    for(i = 0; i <= LIMIT; i++) {
        for(auto x : qq[i]) {
            int node = x.first;
            int idx = x.second;
            int cine = cb(node);
            int pana = query(cine - 1);
            node -= pana;
            sol[idx] = v[poz[cine] + node - 1];
        }
        mShuffle();
    }
    for(i = 1; i <= q; i++) {
        cout << sol[i] << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int cb(int)':
Main.cpp:44:35: warning: unused variable 'sum' [-Wunused-variable]
   44 |     int r = 0, pas = (1 << bits), sum = 0;
      |                                   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 99132 KB Output is correct
2 Correct 863 ms 98124 KB Output is correct
3 Correct 859 ms 97688 KB Output is correct
4 Correct 795 ms 97544 KB Output is correct
5 Correct 866 ms 99792 KB Output is correct
6 Correct 833 ms 100344 KB Output is correct
7 Correct 966 ms 100640 KB Output is correct
8 Correct 826 ms 98996 KB Output is correct
9 Correct 860 ms 97964 KB Output is correct
10 Correct 867 ms 97768 KB Output is correct
11 Correct 799 ms 98176 KB Output is correct
12 Correct 831 ms 96360 KB Output is correct
13 Correct 834 ms 97248 KB Output is correct
14 Correct 991 ms 99488 KB Output is correct
15 Correct 821 ms 97896 KB Output is correct
16 Correct 489 ms 80244 KB Output is correct
17 Correct 768 ms 96744 KB Output is correct
18 Correct 749 ms 96636 KB Output is correct
19 Correct 322 ms 80216 KB Output is correct
20 Correct 316 ms 80212 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1004 ms 104428 KB Output is correct
2 Correct 976 ms 104828 KB Output is correct
3 Correct 1004 ms 100296 KB Output is correct
4 Correct 1128 ms 100428 KB Output is correct
5 Correct 865 ms 100780 KB Output is correct
6 Correct 1099 ms 100268 KB Output is correct
7 Correct 805 ms 104324 KB Output is correct
8 Correct 1043 ms 103440 KB Output is correct
9 Correct 717 ms 100728 KB Output is correct
10 Correct 1006 ms 103244 KB Output is correct
11 Correct 693 ms 100568 KB Output is correct
12 Correct 917 ms 100008 KB Output is correct
13 Correct 1027 ms 103488 KB Output is correct
14 Correct 744 ms 100552 KB Output is correct
15 Correct 1153 ms 103788 KB Output is correct
16 Correct 449 ms 85784 KB Output is correct
17 Correct 975 ms 103432 KB Output is correct
18 Correct 840 ms 98324 KB Output is correct
19 Correct 839 ms 88992 KB Output is correct
20 Correct 727 ms 89220 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 87104 KB Output is correct
2 Correct 531 ms 86144 KB Output is correct
3 Correct 633 ms 86108 KB Output is correct
4 Correct 740 ms 85792 KB Output is correct
5 Correct 638 ms 86184 KB Output is correct
6 Correct 740 ms 85784 KB Output is correct
7 Correct 522 ms 86176 KB Output is correct
8 Correct 616 ms 85768 KB Output is correct
9 Correct 525 ms 86040 KB Output is correct
10 Correct 598 ms 85708 KB Output is correct
11 Correct 478 ms 85836 KB Output is correct
12 Correct 623 ms 85744 KB Output is correct
13 Correct 594 ms 85708 KB Output is correct
14 Correct 492 ms 85800 KB Output is correct
15 Correct 641 ms 85356 KB Output is correct
16 Correct 497 ms 82844 KB Output is correct
17 Correct 608 ms 85112 KB Output is correct
18 Correct 576 ms 84260 KB Output is correct
19 Correct 302 ms 80332 KB Output is correct
20 Correct 295 ms 80104 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 949 ms 99132 KB Output is correct
2 Correct 863 ms 98124 KB Output is correct
3 Correct 859 ms 97688 KB Output is correct
4 Correct 795 ms 97544 KB Output is correct
5 Correct 866 ms 99792 KB Output is correct
6 Correct 833 ms 100344 KB Output is correct
7 Correct 966 ms 100640 KB Output is correct
8 Correct 826 ms 98996 KB Output is correct
9 Correct 860 ms 97964 KB Output is correct
10 Correct 867 ms 97768 KB Output is correct
11 Correct 799 ms 98176 KB Output is correct
12 Correct 831 ms 96360 KB Output is correct
13 Correct 834 ms 97248 KB Output is correct
14 Correct 991 ms 99488 KB Output is correct
15 Correct 821 ms 97896 KB Output is correct
16 Correct 489 ms 80244 KB Output is correct
17 Correct 768 ms 96744 KB Output is correct
18 Correct 749 ms 96636 KB Output is correct
19 Correct 322 ms 80216 KB Output is correct
20 Correct 316 ms 80212 KB Output is correct
21 Correct 1004 ms 104428 KB Output is correct
22 Correct 976 ms 104828 KB Output is correct
23 Correct 1004 ms 100296 KB Output is correct
24 Correct 1128 ms 100428 KB Output is correct
25 Correct 865 ms 100780 KB Output is correct
26 Correct 1099 ms 100268 KB Output is correct
27 Correct 805 ms 104324 KB Output is correct
28 Correct 1043 ms 103440 KB Output is correct
29 Correct 717 ms 100728 KB Output is correct
30 Correct 1006 ms 103244 KB Output is correct
31 Correct 693 ms 100568 KB Output is correct
32 Correct 917 ms 100008 KB Output is correct
33 Correct 1027 ms 103488 KB Output is correct
34 Correct 744 ms 100552 KB Output is correct
35 Correct 1153 ms 103788 KB Output is correct
36 Correct 449 ms 85784 KB Output is correct
37 Correct 975 ms 103432 KB Output is correct
38 Correct 840 ms 98324 KB Output is correct
39 Correct 839 ms 88992 KB Output is correct
40 Correct 727 ms 89220 KB Output is correct
41 Correct 547 ms 87104 KB Output is correct
42 Correct 531 ms 86144 KB Output is correct
43 Correct 633 ms 86108 KB Output is correct
44 Correct 740 ms 85792 KB Output is correct
45 Correct 638 ms 86184 KB Output is correct
46 Correct 740 ms 85784 KB Output is correct
47 Correct 522 ms 86176 KB Output is correct
48 Correct 616 ms 85768 KB Output is correct
49 Correct 525 ms 86040 KB Output is correct
50 Correct 598 ms 85708 KB Output is correct
51 Correct 478 ms 85836 KB Output is correct
52 Correct 623 ms 85744 KB Output is correct
53 Correct 594 ms 85708 KB Output is correct
54 Correct 492 ms 85800 KB Output is correct
55 Correct 641 ms 85356 KB Output is correct
56 Correct 497 ms 82844 KB Output is correct
57 Correct 608 ms 85112 KB Output is correct
58 Correct 576 ms 84260 KB Output is correct
59 Correct 302 ms 80332 KB Output is correct
60 Correct 295 ms 80104 KB Output is correct
61 Correct 1182 ms 110816 KB Output is correct
62 Correct 1043 ms 109644 KB Output is correct
63 Correct 1193 ms 108688 KB Output is correct
64 Correct 1237 ms 108512 KB Output is correct
65 Correct 1022 ms 109660 KB Output is correct
66 Correct 1203 ms 108356 KB Output is correct
67 Correct 815 ms 107540 KB Output is correct
68 Correct 1004 ms 106520 KB Output is correct
69 Correct 806 ms 108460 KB Output is correct
70 Correct 1018 ms 105292 KB Output is correct
71 Correct 751 ms 107664 KB Output is correct
72 Correct 1044 ms 105636 KB Output is correct
73 Correct 1020 ms 106676 KB Output is correct
74 Correct 810 ms 107764 KB Output is correct
75 Correct 1094 ms 106700 KB Output is correct
76 Correct 446 ms 84684 KB Output is correct
77 Correct 1083 ms 102464 KB Output is correct
78 Correct 915 ms 100916 KB Output is correct
79 Correct 296 ms 80220 KB Output is correct
80 Correct 315 ms 80212 KB Output is correct