oj.uz

Submission #684700

# Submission time Handle Problem Language Result Execution time Memory
684700 2023-01-22T10:57:41 Z US3RN4M3 The Potion of Great Power (CEOI20_potion) C++17
38 / 100
 3000 ms 77104 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);
		}
	}
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
	reduce(v1);
	reduce(v2);
	vector<pair<int, int>> evt;
	for(int i : v1) evt.push_back({i, 1});
	for(int i : v2) evt.push_back({i, 2});
	sort(evt.begin(), evt.end());
	int last1 = -1e9, last2 = -1e9;
	int ans = 1e9;
	for(auto [val, type] : evt) {
		if(type == 1) {
			last1 = vals[val];
		} else {
			last2 = vals[val];
		}
		ans = min(ans, abs(last1 - last2));
	}
	return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 74264 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 74184 KB Output is correct
2 Correct 51 ms 74100 KB Output is correct
3 Correct 53 ms 74224 KB Output is correct
4 Correct 75 ms 75328 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 76992 KB Output is correct
2 Correct 257 ms 76852 KB Output is correct
3 Correct 352 ms 76944 KB Output is correct
4 Correct 1765 ms 75732 KB Output is correct
5 Correct 483 ms 75932 KB Output is correct
6 Execution timed out 3052 ms 76836 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 77052 KB Output is correct
2 Execution timed out 3060 ms 77104 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 74312 KB Output is correct
2 Correct 191 ms 74372 KB Output is correct
3 Correct 330 ms 74276 KB Output is correct
4 Correct 1054 ms 74364 KB Output is correct
5 Correct 1004 ms 74372 KB Output is correct
6 Correct 231 ms 74148 KB Output is correct
7 Correct 1224 ms 74276 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 74264 KB Output is correct
2 Correct 58 ms 74184 KB Output is correct
3 Correct 51 ms 74100 KB Output is correct
4 Correct 53 ms 74224 KB Output is correct
5 Correct 75 ms 75328 KB Output is correct
6 Correct 262 ms 76992 KB Output is correct
7 Correct 257 ms 76852 KB Output is correct
8 Correct 352 ms 76944 KB Output is correct
9 Correct 1765 ms 75732 KB Output is correct
10 Correct 483 ms 75932 KB Output is correct
11 Execution timed out 3052 ms 76836 KB Time limit exceeded
12 Halted 0 ms 0 KB -