Submission #716577

#	Time	Username	Problem	Language	Result	Execution time	Memory
716577		Arturgo	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	2245 ms	55976 KiB

Main

#include <bits/stdc++.h>
using namespace std;

struct Arbre {
	int rd, l, r;
	int lb, rb;
	int sz;
	
	Arbre(int _lb, int _rb) {
		rd = rand();
		lb = _lb;
		rb = _rb;
		l = r = -1;
		sz = rb - lb;
	}
};

int root = -1;
vector<Arbre> arbres;

int N, Q;

vector<int> nbs;
vector<int> nextBig;

int sz(int a) {
	if(a == -1) return 0;
	return arbres[a].sz;
}

void pull(int a) {
	arbres[a].sz = (arbres[a].rb - arbres[a].lb) + sz(arbres[a].l) + sz(arbres[a].r);
}

int merge(int a, int b) {
	if(a == -1) return b;
	if(b == -1) return a;
	
	if(arbres[a].rd < arbres[b].rd) {
		arbres[a].r = merge(arbres[a].r, b);
		pull(a);
		return a;
	}
	else {
		arbres[b].l = merge(a, arbres[b].l);
		pull(b);
		return b;
	}
}

pair<int, int> split(int a, int x) {
	if(a == -1) return {-1, -1};
	
	if(nbs[arbres[a].lb] < x) {
		pair<int, int> rht = split(arbres[a].r, x);
		arbres[a].r = -1;
		pull(a);
		return {merge(a, rht.first), rht.second};
	}
	else {
		pair<int, int> lft = split(arbres[a].l, x);
		arbres[a].l = -1;
		pull(a);
		return {lft.first, merge(lft.second, a)};
	}
}

int insert(int root, int lb, int ub) {
	pair<int, int> spl = split(root, nbs[lb]);
	int id = arbres.size();
	arbres.push_back(Arbre(lb, ub));
	return merge(merge(spl.first, id), spl.second);
}

int remove(int root, int x) {
	pair<int, int> spl1 = split(root, x);
	pair<int, int> spl2 = split(spl1.second, x + 1);
	return merge(spl1.first, spl2.second);
}

struct Inter {
	int l, r;
	int li, ri;
};

Inter inter_pos(int a, int pos) {
	if(pos < sz(arbres[a].l)) {
		return inter_pos(arbres[a].l, pos);
	}
	pos -= sz(arbres[a].l);
	
	if(pos < arbres[a].rb - arbres[a].lb) {
		return {sz(arbres[a].l), sz(arbres[a].l) + arbres[a].rb - arbres[a].lb, arbres[a].lb, arbres[a].rb};
	}
	pos -= (arbres[a].rb - arbres[a].lb);
	
	Inter res = inter_pos(arbres[a].r, pos);
	res.l += sz(arbres[a].l) + (arbres[a].rb - arbres[a].lb);
	res.r += sz(arbres[a].l) + (arbres[a].rb - arbres[a].lb);
	return res;
}

void debug(int root) {
	if(root == -1) return;
	debug(arbres[root].l);
	cerr << arbres[root].lb << " " << arbres[root].rb << endl;
	debug(arbres[root].r);
}

void init() {
	vector<int> ouverts;
	
	nextBig = vector<int>(N);
	for(int pos = N - 1;pos >= 0;pos--) {
		while(!ouverts.empty() 
		&& nbs[ouverts.back()] <= nbs[pos])
			ouverts.pop_back();
		
		if(ouverts.empty()) nextBig[pos] = N;
		else nextBig[pos] = ouverts.back();
		
		ouverts.push_back(pos);
	}
	
	int start = 0;
	while(start != N) {
		root = insert(root, start, nextBig[start]);
		start = nextBig[start];
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> N >> Q;
	
	for(int i = 0;i < N;i++) {
		int x;
		cin >> x;
		nbs.push_back(x);
	}
	
	init();
	
	vector<vector<pair<int, int>>> reqs(1 + N);
	for(int i = 0;i < Q;i++) {
		int t, j;
		cin >> t >> j;
		reqs[min(N, t)].push_back({i, j - 1});
	}
	
	vector<int> ans(Q);
	
	for(int t = 0;t <= N;t++) {
		// Answer requests
		
		//cerr << "cur: " << t << endl;
		//debug(root);
		
		for(pair<int, int> req : reqs[t]) {
			//cerr << "req: " << req.second << " " << req.first << endl;
			
			Inter inter = inter_pos(root, req.second);
			//cerr << "ans : " << nbs[inter.li + req.second - inter.l] << endl;
			ans[req.first] = nbs[inter.li + req.second - inter.l];
		}
		
		// Split in the middle & reorder
		Inter spl = inter_pos(root, N / 2);
		
		if(spl.l == N / 2) continue;
		
		root = remove(root, nbs[spl.li]);
		
		vector<pair<int, int>> inters;
		inters.push_back({spl.li, spl.li + (N / 2 - spl.l)});
		
		int start = spl.li + N / 2 - spl.l;
		
		while(start != spl.ri) {
			inters.push_back({
				start, 
				min(nextBig[start], spl.ri)
			});
			start = min(nextBig[start], spl.ri);
		}
		
		for(pair<int, int> inter : inters) {
			root = insert(root, inter.first, inter.second);
		}
	}
	
	for(int i = 0;i < Q;i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

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