oj.uz

Submission #954694

# Submission time Handle Problem Language Result Execution time Memory
954694 2024-03-28T11:11:35 Z LucaIlie Abracadabra (CEOI22_abracadabra) C++17
25 / 100
 274 ms 28828 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5 + 10;

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_N + 1];
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 28828 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 274 ms 28020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 13908 KB Output is correct
2 Correct 92 ms 13404 KB Output is correct
3 Correct 96 ms 13516 KB Output is correct
4 Correct 93 ms 12968 KB Output is correct
5 Correct 90 ms 13288 KB Output is correct
6 Correct 82 ms 12720 KB Output is correct
7 Correct 91 ms 12908 KB Output is correct
8 Correct 87 ms 12644 KB Output is correct
9 Correct 87 ms 13212 KB Output is correct
10 Correct 85 ms 12364 KB Output is correct
11 Correct 81 ms 12676 KB Output is correct
12 Correct 75 ms 12372 KB Output is correct
13 Correct 77 ms 12516 KB Output is correct
14 Correct 78 ms 12624 KB Output is correct
15 Correct 75 ms 12372 KB Output is correct
16 Correct 31 ms 11356 KB Output is correct
17 Correct 70 ms 12976 KB Output is correct
18 Correct 67 ms 11876 KB Output is correct
19 Correct 2 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 28828 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -