Submission #745951

#	Time	Username	Problem	Language	Result	Execution time	Memory
745951		MrBrionix	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	1616 ms	53516 KiB

Main

#include<bits/stdc++.h>
using namespace std;
mt19937 rng(time(nullptr));

using T = int;
struct node {
    T val, ma;
    int size;
    size_t prior;
    node *left, *right;

    node(T v) : val(v), ma(v), size(1),
             prior(rng()), left(0), right(0) {}

    node* fix() {
        ma = val, size = 1;
        if (left) {
            ma = max(ma, left->ma);
            size += left->size;
        }
        if (right) {
            ma = max(ma, right->ma);
            size += right->size;
        }
        return this;
    }
};

node* merge(node* a, node* b) {
    if (!a) return b; a->fix();
    if (!b) return a; b->fix();
    if (a->prior > b->prior) {
        a->right = merge(a->right, b);
        return a->fix();
    } else {
        b->left = merge(a, b->left);
        return b->fix();
    }
}

pair<node*, node*> split(node* p, int k) {
    if (!p) return {nullptr, nullptr};
    p->fix();
    int sl = p->left ? p->left->size : 0;
    if (k <= sl) {
        auto [a, b] = split(p->left, k);
        p->left = b;
        return {a, p->fix()};
    } else {
        auto [a, b] = split(p->right, k-sl-1);
        p->right = a;
        return {p->fix(), b};
    }
}

int find_kth(node* p,int pos){
    p->fix();
    int sl = p->left ? p->left->size : 0;
    if (p->left && pos < sl) {
        return find_kth(p->left,pos);
    } else if (p->right && pos > sl) {
        return find_kth(p->right,pos - sl - 1);
    } else {
        return p->val;
    }
}

int find_first(node *p,int val){
    int sl = p->left ? p->left->size : 0;
    if (p->left && p->left->ma > val) {
        return find_first(p->left,val);
    } else if (p->val > val){
		return sl;
	} else if (p->right && p->right->ma > val) {
        return sl + 1 + find_first(p->right,val);
    } else {
        return p->size;
    }
}

node* build(vector<T>& A, int l, int r) {
    if (l + 1 == r) return new node(A[l]);
    int m = (l + r) / 2;
    node* a = build(A, l, m);
    node* b = build(A, m, r);
    return merge(a, b);
}


const int MAXN = 200005, MAXQ = 1000006;
int n,q,ans[MAXQ],tmp[MAXN],cont;
vector<T> v;
vector<pair<int,int> > opz[MAXN];
node* root;

int main(){

	ios::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>q;
	v.resize(n);
	
	for(int i=0;i<n;i++){
		cin>>v[i];
	}
	
	for(int i=0;i<q;i++){
		int t,x;
		cin>>t>>x;
		opz[min(t,n)].emplace_back(x-1,i);
	}
	root = build(v,0,n);
	
	for(int i=0;i<=n;i++){
		for(auto [a,b] : opz[i]){
			ans[b]=find_kth(root,a);
		}
		
		auto [a,b] = split(root,n/2);
		
		while(b!=nullptr){
			int val = find_kth(b,0);
			
			if(val > a->ma){
				a = merge(a,b);
				break;
			}
			
			int pos1 = find_first(a,val);
			int pos2 = find_first(b,val);
			
			auto [c,d] = split(b,pos2);
			auto [e,f] = split(a,pos1);
			
			a = merge(merge(e,c),f);
			b = d;
			cont++;
		}
		root = a;
	}

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

Compilation message (stderr)

Main.cpp: In function 'node* merge(node*, node*)':
Main.cpp:30:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   30 |     if (!a) return b; a->fix();
      |     ^~
Main.cpp:30:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |     if (!a) return b; a->fix();
      |                       ^
Main.cpp:31:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   31 |     if (!b) return a; b->fix();
      |     ^~
Main.cpp:31:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   31 |     if (!b) return a; b->fix();
      |                       ^

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