Submission #954692

#	Time	Username	Problem	Language	Result	Execution time	Memory
954692		LucaIlie	Abracadabra (CEOI22_abracadabra)	C++17	25 / 100	260 ms	28760 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;

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
• Subtask 2: 0 / 40
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25