oj.uz

Submission #954695

# Submission time Handle Problem Language Result Execution time Memory
954695 2024-03-28T11:12:27 Z LucaIlie Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 928 ms 55840 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;
const int MAX_Q = 2e6;

struct query {
    int t, p, q, ans;
};

struct AIB {
    int aib[MAX_N + 1];

    void update( int i, int x ) {
        while ( i <= MAX_N ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int s = 0;
        while ( i > 0 ) {
            s += aib[i];
            i -= (i & -i);
        }
        return s;
    }

    int lastLower( int x ) {
        int pos = 0;
        for ( int p = log2( MAX_N ); p >= 0; p-- ) {
            if ( pos + (1 << p) <= MAX_N && x - aib[pos + (1 << p)] > 0 ) {
                pos += (1 << p);
                x -= aib[pos];
            }
        }
        return pos;
    }
} groups;

int perm[MAX_N + 1], pos[MAX_N + 1], firstGreater[MAX_N + 1], sizee[MAX_N + 1];
query queries[MAX_Q];
vector<int> queriesByTime[MAX_N + 1];

int main() {
    int n, q;

    cin >> n >> q;
    for ( int i = 1; i <= n; i++ ) {
        cin >> perm[i];
        pos[perm[i]] = i;
    }
    for ( int i = 0; i < q; i++ ) {
        cin >> queries[i].t >> queries[i].p;
        queries[i].t = min( queries[i].t, n );
        queries[i].q = i;
        queriesByTime[queries[i].t].push_back( i );
    }

    vector<int> stack;
    perm[n + 1] = n + 1;
    stack.push_back( n + 1 );
    for ( int i = n; i >= 1; i-- ) {
        while ( !stack.empty() && perm[i] > perm[stack.back()] )
            stack.pop_back();
        firstGreater[i] = stack.back();
        stack.push_back( i );
    }

    for ( int q: queriesByTime[0] )
        queries[q].ans = perm[queries[q].p];

    int i = 1;
    while ( i <= n / 2 ) {
        sizee[perm[i]] = min( n / 2 + 1, firstGreater[i] ) - i;
        groups.update( perm[i], sizee[perm[i]] );
        i = firstGreater[i];
    }
    i = n / 2 + 1;
    while ( i <= n ) {
        sizee[perm[i]] = firstGreater[i] - i;
        groups.update( perm[i], sizee[perm[i]] );
        i = firstGreater[i];
    }
    for ( int t = 1; t <= n; t++ ) {
        for ( int q: queriesByTime[t] ) {
            int g = groups.lastLower( queries[q].p ) + 1;
            int x = groups.query( g - 1 );
            queries[q].ans = perm[pos[g] + queries[q].p - x - 1];
        }

        int g = groups.lastLower( n / 2 ) + 1;
        int x = groups.query( g - 1 );
        if ( sizee[g] == n / 2 - x )
            continue;

        int i = pos[g] + n / 2 - x;
        while ( i < pos[g] + sizee[g]) {
            sizee[perm[i]] = min( pos[g] + sizee[g], firstGreater[i] ) - i;
            groups.update( perm[i], sizee[perm[i]] );
            i = firstGreater[i];
        }

        groups.update( g, -sizee[g] );
        sizee[g] = n / 2 - x;
        groups.update( g, sizee[g] );
    }

    for ( int i = 0; i < q; i++ )
        cout << queries[i].ans << "\n";

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 38500 KB Output is correct
2 Correct 490 ms 40868 KB Output is correct
3 Correct 455 ms 40784 KB Output is correct
4 Correct 422 ms 39772 KB Output is correct
5 Correct 472 ms 41740 KB Output is correct
6 Correct 416 ms 41300 KB Output is correct
7 Correct 505 ms 42476 KB Output is correct
8 Correct 426 ms 40788 KB Output is correct
9 Correct 423 ms 40528 KB Output is correct
10 Correct 421 ms 39760 KB Output is correct
11 Correct 414 ms 39792 KB Output is correct
12 Correct 369 ms 38268 KB Output is correct
13 Correct 401 ms 39660 KB Output is correct
14 Correct 474 ms 40932 KB Output is correct
15 Correct 422 ms 40348 KB Output is correct
16 Correct 2 ms 10840 KB Output is correct
17 Correct 320 ms 38584 KB Output is correct
18 Correct 342 ms 38328 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 43480 KB Output is correct
2 Correct 581 ms 51380 KB Output is correct
3 Correct 468 ms 44348 KB Output is correct
4 Correct 516 ms 43476 KB Output is correct
5 Correct 478 ms 44256 KB Output is correct
6 Correct 481 ms 42740 KB Output is correct
7 Correct 566 ms 49772 KB Output is correct
8 Correct 565 ms 48656 KB Output is correct
9 Correct 470 ms 42820 KB Output is correct
10 Correct 550 ms 47548 KB Output is correct
11 Correct 440 ms 41680 KB Output is correct
12 Correct 450 ms 42716 KB Output is correct
13 Correct 572 ms 46772 KB Output is correct
14 Correct 459 ms 42100 KB Output is correct
15 Correct 571 ms 48444 KB Output is correct
16 Correct 54 ms 12624 KB Output is correct
17 Correct 421 ms 46772 KB Output is correct
18 Correct 401 ms 38836 KB Output is correct
19 Correct 138 ms 18480 KB Output is correct
20 Correct 179 ms 19996 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 14676 KB Output is correct
2 Correct 94 ms 14100 KB Output is correct
3 Correct 93 ms 14384 KB Output is correct
4 Correct 104 ms 13484 KB Output is correct
5 Correct 93 ms 13916 KB Output is correct
6 Correct 84 ms 13420 KB Output is correct
7 Correct 88 ms 13860 KB Output is correct
8 Correct 84 ms 13648 KB Output is correct
9 Correct 90 ms 13648 KB Output is correct
10 Correct 75 ms 13396 KB Output is correct
11 Correct 76 ms 13396 KB Output is correct
12 Correct 76 ms 13456 KB Output is correct
13 Correct 77 ms 13392 KB Output is correct
14 Correct 90 ms 13680 KB Output is correct
15 Correct 75 ms 13308 KB Output is correct
16 Correct 28 ms 11612 KB Output is correct
17 Correct 64 ms 13644 KB Output is correct
18 Correct 82 ms 12964 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 38500 KB Output is correct
2 Correct 490 ms 40868 KB Output is correct
3 Correct 455 ms 40784 KB Output is correct
4 Correct 422 ms 39772 KB Output is correct
5 Correct 472 ms 41740 KB Output is correct
6 Correct 416 ms 41300 KB Output is correct
7 Correct 505 ms 42476 KB Output is correct
8 Correct 426 ms 40788 KB Output is correct
9 Correct 423 ms 40528 KB Output is correct
10 Correct 421 ms 39760 KB Output is correct
11 Correct 414 ms 39792 KB Output is correct
12 Correct 369 ms 38268 KB Output is correct
13 Correct 401 ms 39660 KB Output is correct
14 Correct 474 ms 40932 KB Output is correct
15 Correct 422 ms 40348 KB Output is correct
16 Correct 2 ms 10840 KB Output is correct
17 Correct 320 ms 38584 KB Output is correct
18 Correct 342 ms 38328 KB Output is correct
19 Correct 2 ms 10840 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 599 ms 43480 KB Output is correct
22 Correct 581 ms 51380 KB Output is correct
23 Correct 468 ms 44348 KB Output is correct
24 Correct 516 ms 43476 KB Output is correct
25 Correct 478 ms 44256 KB Output is correct
26 Correct 481 ms 42740 KB Output is correct
27 Correct 566 ms 49772 KB Output is correct
28 Correct 565 ms 48656 KB Output is correct
29 Correct 470 ms 42820 KB Output is correct
30 Correct 550 ms 47548 KB Output is correct
31 Correct 440 ms 41680 KB Output is correct
32 Correct 450 ms 42716 KB Output is correct
33 Correct 572 ms 46772 KB Output is correct
34 Correct 459 ms 42100 KB Output is correct
35 Correct 571 ms 48444 KB Output is correct
36 Correct 54 ms 12624 KB Output is correct
37 Correct 421 ms 46772 KB Output is correct
38 Correct 401 ms 38836 KB Output is correct
39 Correct 138 ms 18480 KB Output is correct
40 Correct 179 ms 19996 KB Output is correct
41 Correct 98 ms 14676 KB Output is correct
42 Correct 94 ms 14100 KB Output is correct
43 Correct 93 ms 14384 KB Output is correct
44 Correct 104 ms 13484 KB Output is correct
45 Correct 93 ms 13916 KB Output is correct
46 Correct 84 ms 13420 KB Output is correct
47 Correct 88 ms 13860 KB Output is correct
48 Correct 84 ms 13648 KB Output is correct
49 Correct 90 ms 13648 KB Output is correct
50 Correct 75 ms 13396 KB Output is correct
51 Correct 76 ms 13396 KB Output is correct
52 Correct 76 ms 13456 KB Output is correct
53 Correct 77 ms 13392 KB Output is correct
54 Correct 90 ms 13680 KB Output is correct
55 Correct 75 ms 13308 KB Output is correct
56 Correct 28 ms 11612 KB Output is correct
57 Correct 64 ms 13644 KB Output is correct
58 Correct 82 ms 12964 KB Output is correct
59 Correct 2 ms 10840 KB Output is correct
60 Correct 2 ms 10844 KB Output is correct
61 Correct 928 ms 55840 KB Output is correct
62 Correct 787 ms 53956 KB Output is correct
63 Correct 778 ms 53380 KB Output is correct
64 Correct 733 ms 52048 KB Output is correct
65 Correct 704 ms 53096 KB Output is correct
66 Correct 732 ms 51904 KB Output is correct
67 Correct 658 ms 51284 KB Output is correct
68 Correct 654 ms 50280 KB Output is correct
69 Correct 686 ms 51532 KB Output is correct
70 Correct 633 ms 49168 KB Output is correct
71 Correct 568 ms 49600 KB Output is correct
72 Correct 630 ms 49236 KB Output is correct
73 Correct 617 ms 49304 KB Output is correct
74 Correct 640 ms 50620 KB Output is correct
75 Correct 636 ms 49752 KB Output is correct
76 Correct 53 ms 12964 KB Output is correct
77 Correct 434 ms 46784 KB Output is correct
78 Correct 513 ms 44660 KB Output is correct
79 Correct 2 ms 10876 KB Output is correct
80 Correct 2 ms 10844 KB Output is correct