oj.uz

Submission #684703

# Submission time Handle Problem Language Result Execution time Memory
684703 2023-01-22T11:00:35 Z US3RN4M3 The Potion of Great Power (CEOI20_potion) C++17
52 / 100
 3000 ms 77116 KB 
#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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 74184 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 74108 KB Output is correct
2 Correct 50 ms 74184 KB Output is correct
3 Correct 62 ms 74148 KB Output is correct
4 Correct 73 ms 75348 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 77116 KB Output is correct
2 Correct 271 ms 76828 KB Output is correct
3 Correct 373 ms 76872 KB Output is correct
4 Correct 1216 ms 75752 KB Output is correct
5 Correct 434 ms 76048 KB Output is correct
6 Correct 2739 ms 76912 KB Output is correct
7 Correct 564 ms 76888 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 464 ms 77028 KB Output is correct
2 Execution timed out 3039 ms 77036 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 74312 KB Output is correct
2 Correct 180 ms 74272 KB Output is correct
3 Correct 304 ms 74312 KB Output is correct
4 Correct 698 ms 74440 KB Output is correct
5 Correct 632 ms 74360 KB Output is correct
6 Correct 179 ms 74172 KB Output is correct
7 Correct 991 ms 74392 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 74184 KB Output is correct
2 Correct 57 ms 74108 KB Output is correct
3 Correct 50 ms 74184 KB Output is correct
4 Correct 62 ms 74148 KB Output is correct
5 Correct 73 ms 75348 KB Output is correct
6 Correct 283 ms 77116 KB Output is correct
7 Correct 271 ms 76828 KB Output is correct
8 Correct 373 ms 76872 KB Output is correct
9 Correct 1216 ms 75752 KB Output is correct
10 Correct 434 ms 76048 KB Output is correct
11 Correct 2739 ms 76912 KB Output is correct
12 Correct 564 ms 76888 KB Output is correct
13 Correct 464 ms 77028 KB Output is correct
14 Execution timed out 3039 ms 77036 KB Time limit exceeded
15 Halted 0 ms 0 KB -