Submission #1228734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228734		trideser	Abracadabra (CEOI22_abracadabra)	C++20	100 / 100	1657 ms	48788 KiB

Main

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

struct Treap {
	int l = -1;
	int r = -1;
	int stsize = 1;
	int p = -1;
	int val;
	int prio;
	Treap(int val, int prio) : val(val), prio(prio) {
	}
};

vector<Treap> nodes;

int merge(int l, int r) {
	if(l == -1)
		return r;
	if(r == -1)
		return l;
	////cerr << nodes[l].val << " " << nodes[r].val << "\n";
	int newstsize = nodes[l].stsize + nodes[r].stsize;
	if(nodes[l].prio < nodes[r].prio) {
		////cerr << "L\n";
		int a = merge(nodes[l].r, r);
		nodes[l].r = a;
		if(nodes[l].r != -1)
			nodes[nodes[l].r].p = l;
		nodes[l].stsize = newstsize;
		return l;
	}
	else {
		////cerr << "R\n";
		int a = merge(l, nodes[r].l);
		nodes[r].l = a;
		if(nodes[r].l != -1)
			nodes[nodes[r].l].p = r;
		nodes[r].stsize = newstsize;
		return r;
	}
}
pair<int, int> split(int t, int size) {
	if(t == -1)
		return make_pair(-1, -1);
	int lstsize = (nodes[t].l == -1 ? 0 : nodes[nodes[t].l].stsize) + 1;
	if(lstsize <= size) {
		pair<int, int> a = split(nodes[t].r, size - lstsize);
		nodes[t].r = a.first;
		if(nodes[t].r != -1)
			nodes[nodes[t].r].p = t;
		if(a.second != -1)
			nodes[a.second].p = -1;
		
		nodes[t].stsize = (nodes[t].l == -1 ? 0 : nodes[nodes[t].l].stsize) + (nodes[t].r == -1 ? 0 : nodes[nodes[t].r].stsize) + 1;
		return make_pair(t, a.second);
	}
	else {
		pair<int, int> a = split(nodes[t].l, size);
		nodes[t].l = a.second;
		if(nodes[t].l != -1)
			nodes[nodes[t].l].p = t;
		if(a.first != -1)
			nodes[a.first].p = -1;

		nodes[t].stsize = (nodes[t].l == -1 ? 0 : nodes[nodes[t].l].stsize) + (nodes[t].r == -1 ? 0 : nodes[nodes[t].r].stsize) + 1;
		return make_pair(a.first, t);
	}
}

int get_index(int t, int child) {
	if(t == -1)
		return 0;
	////cerr << "gi: "<< nodes[t].val << "\n";
	if(nodes[t].l != -1 && nodes[t].l != child) {
		return nodes[nodes[t].l].stsize + get_index(nodes[t].p, t) + 1;
	}
	if(nodes[t].l != child || child == -1) {
		return get_index(nodes[t].p, t) + 1;
	}
	return get_index(nodes[t].p, t) ;
}

void print(int t) {
	if(t == -1)
		return;
	//print(nodes[t].l);
	//cerr << nodes[t].val << " " << nodes[t].prio << " " << nodes[t].stsize << " " << nodes[t].p << "\n";
	//print(nodes[t].r);
}

int main() {
	mt19937 rng(89);
	int N, Q;
	cin >> N;
	cin >> Q;
	vector<int> init(N);
	vector<int> prio(N);
	int root = -1;
	for(int i = 0; i < N; i++) {
		int a;
		cin >> a;
		init[i] = a;
		prio[i] = i;
	}
	shuffle(prio.begin(), prio.end(), rng);
	for(int i = 0; i < N; i++) {
		nodes.push_back(Treap(init[i], prio[i]));
		root = merge(root, nodes.size() - 1);
	}
	vector<tuple<int, int, int>> queries(Q);
	for(int j = 0; j < Q; j++) {
		int t, i;
		cin >> t;
		cin >> i;
		queries[j] = make_tuple(t, i, j);
	}

	sort(queries.begin(), queries.end()); // TODO bucketsort
	int qindex = 0;
	vector<int> query_answers(Q, -1);
	map<int, int> next;
	vector<int> interval(N);
	for(int i = N - 1; i >= 0; i--) {
		auto it = next.upper_bound(init[i]);
		if(it == next.end()) {
			interval[i] = N - 1;
			next.clear();
			next[init[i]] = i;
			continue;
		}
		interval[i] = it->second - 1;
		for(auto del = next.begin(); del!= it; del = next.begin()) {
			next.erase(del);
		}
		next[init[i]] = i;
		
	}
	vector<int> init_inverse(N + 1, -1);
	for(int i = 0; i < N; i++) {
		init_inverse[init[i]] = i;
	}
	
	for(int a : init) {
			//cerr << a << " ";
	}
	//cerr << "\n";
	for(int a : init_inverse) {
		//cerr << a << " ";
	}
	//cerr << "\n";

	for(int a : interval) {
		//cerr << a << " ";
	}
	//cerr << "\n";

	int ix = 0;
	int ss = 0;
	vector<int> segment(N);
	vector<int> segment_begin(N, -1);
	set<int> segs;
	while(ix < N) {
		int k = ix;
		segment_begin[ss] = k;
		segs.insert(init[ix]);
		while(ix <= interval[k]) {
			segment[ix] = ss;
			ix++;
		}
		ss++;
	}
	
	

	for(int a : segment) {
		//cerr << a << " ";
	}
	//cerr << "\n";
	for(int a : segment_begin) {
		//cerr << a << " ";
	}
	//cerr << "\n";
	//cerr << "TREAP:\n";
	//print(root);
	//cerr<<"\n\n";
	int shuffles = 0;
	while(shuffles < N) {
		//cerr << shuffles;
		bool b = false;
		while(get<0>(queries[qindex]) == shuffles) {
			int left, center, right;
			tie(left, center) = split(root, get<1>(queries[qindex]) - 1);
			tie(center, right) = split(center, 1);
			//cerr << get<2>(queries[qindex]) << "RRR\n";
			query_answers[get<2>(queries[qindex])] = nodes[center].val;
			root = merge(merge(left, center), right);
			qindex++;
			if(qindex == Q) {
				b = true;
				break;
			}
		}
		if(b){
			break;
		}
		int left, center, right;
		tie(left, center) = split(root, N / 2);
		tie(center, right) = split(center, 1);
		int centercp = center;
		//cerr << left << " " << right << "\n";
		//print(left);
		//cerr << "\n";
		//print(center);
		//cerr << "\n";
		//print(right);
		//cerr << "\n";
		int cseg = segment[init_inverse[nodes[center].val]];
		root = merge(merge(left, center), right);
		int cseg_begin = segment_begin[cseg];
		int cseg_end = interval[cseg_begin];
		int cseg_mid = init_inverse[nodes[centercp].val];
		//cerr << "cseg: " << cseg << " " << cseg_begin << " " << cseg_mid << " " << cseg_end << "\n";
		
		if(cseg_begin == cseg_mid) {
			break;
		}
		int lgsegend = cseg_mid - 1;
		int lgsegsize = lgsegend - cseg_begin + 1;
		int lgseg = cseg_begin;
		vector<int> csegs;
		csegs.push_back(cseg_begin);
		int i = cseg_mid;
		//cerr << "START i: " << i << "\n";
		while(i <= cseg_end) {
			int nend = min(interval[i], cseg_end);
			int nendsz = nend - i + 1;
			if(nendsz > lgsegsize) {
				lgseg = i;
				lgsegsize = nendsz;
				lgsegend = nend;
			}
			//cerr << "NEND: " << nend << " " << nendsz << "\n";
			csegs.push_back(i);
			i = nend + 1;
		}
		//cerr << "LGSEG LGSEGSIZE: " << lgseg << " " << lgsegsize << " " << lgsegend << "\n";
		interval[cseg_begin] = cseg_mid - 1;

		for(int seg : csegs) {
			//cerr << seg << ": ";
			if(seg != cseg_begin) {
				interval[seg] = min(interval[seg], cseg_end);
				//cerr << "moving seg " << seg << "\n";
				int beginnode = seg;
				int endnode = interval[seg]; // not really
				segs.insert(init[seg]);


				//cerr << "ubound: " << ((segs.upper_bound(init[seg]) == segs.end()) ? N : *(segs.upper_bound(init[seg]))) << "\n";
				//cerr << "uix: " << init_inverse[(segs.upper_bound(init[seg]) == segs.end()) ? N : *(segs.upper_bound(init[seg]))] << "\n";
				//cerr << "nodes: " << beginnode << " " << endnode << "\n";
				int mvindex = get_index(init_inverse[(segs.upper_bound(init[seg]) == segs.end()) ? N : *(segs.upper_bound(init[seg]))], -1) - 1;


				int beginnodeindex = get_index(beginnode, -1);
				int endnodeindex = get_index(endnode, -1);
				//cerr << beginnodeindex << " " << endnodeindex << " " << mvindex << "\n";
				// move seg
				// TODO
				
				int ll, cc, mm, rr;
				tie(mm, rr) = split(root, endnodeindex);
				tie(cc, mm) = split(mm, beginnodeindex - 1); //one before beginning
				tie(ll, cc) = split(cc, mvindex);
				//cerr << "ll:\n";
				//print(ll);
				//cerr << "cc:\n";
				//print(cc);
				//cerr << "mm:\n";
				//print(mm);
				//cerr << "rr:\n";
				//print(rr);
				root = merge(merge(ll, mm), merge(cc, rr));

			}
			if(seg != lgseg) {
				//cerr << "changing seg id\n";
				// change seg id
				int end = seg == cseg_begin ? cseg_mid - 1 : min(interval[seg], cseg_end);
				for(int j = seg; j <= end; j++) {
					segment[j] = ss;
				}
				segment_begin[ss] = seg;
				ss++;
			}
			segment_begin[segment[seg]] = seg;

		}
		//cerr << "\n";
		shuffles++;
		//cerr << "segment: ";
		for(int a : segment) {
			//cerr << a << " ";
		}
		//cerr << "\nsegment_begin: ";
		for(int a : segment_begin) {
			//cerr << a << " ";
		}
		//cerr << "\ninterval: ";
		for(int a : interval) {
			//cerr << a << " ";
		}
		//cerr << "\n";
		for(auto it = segs.begin(); it != segs.end(); it++) {
			//cerr << *it << " ";
		}
		//cerr << "\n\n";
		//print(root);
		//cerr << "\n\n";
	}
	
	while(qindex < Q) {
		int left, center, right;
		tie(left, center) = split(root, get<1>(queries[qindex]) - 1);
		tie(center, right) = split(center, 1);
		//cerr << get<2>(queries[qindex]) << "RRR\n";
		query_answers[get<2>(queries[qindex])] = nodes[center].val;
		root = merge(merge(left, center), right);
		qindex++;
	}
	//print(root);
	//cerr << "\n\n\n";
	//cerr << "END END END: \n";
	for(int a : query_answers)
		cout << a << "\n";
	return 0;
}

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