Submission #684703

#	Time	Username	Problem	Language	Result	Execution time	Memory
684703		US3RN4M3	The Potion of Great Power (CEOI20_potion)	C++17	52 / 100	3039 ms	77116 KiB

potion

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 262144;
pair<int, int> pairs[18][mx*2];
int vals[mx];
int compress[mx];
int n;
void init(int N, int D, int H[]) {
	n = N;
	vector<pair<int, int>> v(N);
	for(int i = 0; i < N; i++) v[i] = {H[i], i};
	sort(v.begin(), v.end());
	for(int i = 0; i < N; i++) {
		vals[i] = v[i].first;
		compress[v[i].second] = i;
	}
}
void init_pairs(int b) {
	for(int stt_pos = 0; stt_pos < mx*2; stt_pos += (2<<b)) {
		int i1 = stt_pos, i2 = stt_pos + (1<<b);
		int e1 = stt_pos + (1<<b);
		int e2 = stt_pos + (2<<b);
		int cur_pos = stt_pos;
		while(i1 != e1 && i2 != e2) {
			if(pairs[b - 1][i1] > pairs[b - 1][i2]) {
				pairs[b][cur_pos++] = pairs[b - 1][i2++];
			} else {
				pairs[b][cur_pos++] = pairs[b - 1][i1++];
			}
		}
		while(i2 != e2) {
			pairs[b][cur_pos++] = pairs[b - 1][i2++];
		}
		while(i1 != e1) {
			pairs[b][cur_pos++] = pairs[b - 1][i1++];
		}
		cur_pos = stt_pos;
		int oth_pos = stt_pos;
		while(oth_pos != e2) {
			if(oth_pos != e2 - 1 && pairs[b][oth_pos] == pairs[b][oth_pos + 1]) {
				oth_pos += 2;
				continue;
			}
			pairs[b][cur_pos++] = pairs[b][oth_pos++];
		}
		while(cur_pos != e2) {
			pairs[b][cur_pos++] = {mx, mx};
		}
	}
}
void curseChanges(int U, int A[], int B[]) {
	for(int i = 0; i < U; i++) {
		int a = compress[A[i]], b = compress[B[i]];
		if(a > b) swap(a, b);
		pairs[0][i*2] = {a, b};
		pairs[0][i*2 + 1] = {b, a};
	}
	for(int i = U; i < mx; i++) {
		pairs[0][i*2] = {mx, mx};
		pairs[1][i*2 + 1] = {mx, mx};
	}
	for(int i = 1; i < 18; i++) init_pairs(i);
}
void add_segment(int b, int pos, int val, vector<int> & v) {
	int cur = pos;
	for(int delta = (1<<b); delta >= 1; delta >>= 1) {
		if(pairs[b][cur + delta].first < val) cur += delta;
	}
	if(cur != pos || pairs[b][cur].first < val)
	cur++;
	while(cur != pos + (2<<b)) {
		if(pairs[b][cur].first != val) return;
		v.push_back(pairs[b][cur].second);
		cur++;
	}
}
void reduce(vector<int> & v) {
	vector<int> tmp;
	int last = -1;
	for(int i : v) {
		if(i == last) {
			last = -1;
			tmp.pop_back();
		} else {
			tmp.push_back(i);
			last = i;
		}
	}
	swap(v, tmp);
}
int question(int x, int y, int v) {
	/*for(int i = 0; i < 16; i++) {
		cout << pairs[0][i].first << " " << pairs[0][i].second << endl;
	}
	cout << endl;
	for(int i = 0; i < 16; i++) {
		cout << pairs[1][i].first << " " << pairs[1][i].second << endl;
	}
	cout << endl;
	for(int i = 0; i < 16; i++) {
		cout << pairs[2][i].first << " " << pairs[2][i].second << endl;
	}
	cout << endl;
	exit(0);*/
	x = compress[x];
	y = compress[y];
	vector<int> v1, v2;
	int cur = 0;
	for(int b = 17; b >= 0; b--) {
		if(cur + (1 << b) <= v) {
			add_segment(b, cur*2, x, v1);
			add_segment(b, cur*2, y, v2);
			cur += (1<<b);
		}
	}
	vector<int> evt;
	for(int i : v1) evt.push_back(i*2);
	for(int i : v2) evt.push_back(i*2 + 1);
	sort(evt.begin(), evt.end());
	reduce(evt);
	int last1 = -1e9, last2 = -1e9;
	int ans = 1e9;
	for(auto val : evt) {
		if(val & 1) {
			last1 = vals[val / 2];
		} else {
			last2 = vals[val / 2];
		}
		ans = min(ans, abs(last1 - last2));
	}
	return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 0 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 30