Submission #867119

#	Time	Username	Problem	Language	Result	Execution time	Memory
867119		Lalic	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	445 ms	46368 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

int tree[4*MAXN];

void upd(int node, int l, int r, int pos, int val){
    if(r<pos || l>pos)
        return;
    if(l==r){
        tree[node]=val;
        return;
    }

    int mid=(l+r)/2;

    upd(node*2, l, mid, pos, val);
    upd(node*2+1, mid+1, r, pos, val);

    tree[node]=tree[node*2]+tree[node*2+1];
}

pii search(int node, int l, int r, int val){
    if(l==r)
        return {l, tree[node]};

    int mid=(l+r)/2;

    if(tree[node*2]>=val)
        return search(node*2, l, mid, val);
    
    pii resp=search(node*2+1, mid+1, r, val-tree[node*2]);
    return {resp.fi, resp.se+tree[node*2]};
}

void solve(){
    int n, q; cin >> n >> q;

    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin >> arr[i];

    vector<pair<pii, int>> query(q);
    for(int i=0;i<q;i++)
        cin >> query[i].fi.fi >> query[i].fi.se, query[i].se=i;

    sort(all(query));
    vector<int> ans(q);

    vector<int> rev(n+1);
    for(int i=0;i<n;i++)
        rev[arr[i]]=i;

    int cnt=0;
    bool foi=0;

    vector<int> nx(n+1);
    set<pii> act;
    for(int i=0;i<n;i++){
        auto curr=act.begin();

        while(curr!=act.end() && curr->fi<arr[i]){
            nx[curr->fi]=i-curr->se;
            curr=act.erase(curr);
        }

        act.insert({arr[i], i});
    }

    for(auto u : act)
        nx[u.fi]=n-u.se;

    vector<int> sz(n+1, 0);
    for(int i=0;i<n;i++){
        sz[arr[i]]=nx[arr[i]];
        upd(1, 1, n, arr[i], nx[arr[i]]);
        i+=(nx[arr[i]]-1);
    }

    for(int i=0;i<q;i++){
        while(!foi && cnt<query[i].fi.fi){
            pii curr=search(1, 1, n, n/2+1);

            if(curr.se-sz[curr.fi]>=n/2){
                foi=1;
                break;
            }

            // cout << cnt << ":\n";
            // for(int i=1;i<=n;i++)
            // 	cout << i << " -> " << sz[i] << "\t\n"[i==n];

            int nwsize=n/2-curr.se+sz[curr.fi];
            // cout << "nwsize= " << nwsize << "\t" << " " << curr.fi << "\n";

            upd(1, 1, n, curr.fi, nwsize);

            int ptr=rev[curr.fi]+nwsize;
            while(ptr<n && rev[curr.fi]+sz[curr.fi]-ptr>0){
            	int at=nx[arr[ptr]];
            	// if(ptr+at<n && arr[ptr+at]>curr.fi) at--;

                upd(1, 1, n, arr[ptr], min(at, rev[curr.fi]+sz[curr.fi]-ptr));
                sz[arr[ptr]]=min(at, rev[curr.fi]+sz[curr.fi]-ptr);
                ptr+=nx[arr[ptr]];
            }

            sz[curr.fi]=nwsize;
            
            cnt++;
        }

        pii resp=search(1, 1, n, query[i].fi.se);
        // cout << "resp.fi = " << resp.fi << "\n";
        ans[query[i].se]=arr[rev[resp.fi]+query[i].fi.se-(resp.se-sz[resp.fi]+1)];
    }

    // cout << cnt << ":\n";
    // for(int i=1;i<=n;i++)
    // 	cout << i << " -> " << sz[i] << "\t\n"[i==n];

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

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int tt=1;
	// cin >> tt;
	while(tt--)
		solve();
}

/*
4 3                                                                                                                                                                                                                                
3 1 2 4                                                                                                                                                                                                                            
0 2                                                                                                                                                                                                                                
1 3                                                                                                                                                                                                                                
2 2

2 3 1 4 -> 1°
1 2 3 4 -> 2°
*/

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25