oj.uz

답안 #684708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684708 2023-01-22T11:04:13 Z US3RN4M3 The Potion of Great Power (CEOI20_potion) C++17
52 / 100
 3000 ms 77048 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());
	int last1 = -1e9, last2 = -1e9;
	int ans = 1e9;
	for(int i = 0; i < evt.size(); i++) {
		if(i != evt.size() - 1 && evt[i] == evt[i + 1]) {
			i++;
			continue;
		}
		if(evt[i] & 1) {
			last1 = vals[evt[i] / 2];
		} else {
			last2 = vals[evt[i] / 2];
		}
		ans = min(ans, abs(last1 - last2));
	}
	return ans;
}

Compilation message

potion.cpp: In function 'int question(int, int, int)':
potion.cpp:123:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i = 0; i < evt.size(); i++) {
      |                 ~~^~~~~~~~~~~~
potion.cpp:124:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |   if(i != evt.size() - 1 && evt[i] == evt[i + 1]) {
      |      ~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 74088 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 74184 KB Output is correct
2 Correct 63 ms 74124 KB Output is correct
3 Correct 67 ms 74196 KB Output is correct
4 Correct 84 ms 75360 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 76912 KB Output is correct
2 Correct 274 ms 76916 KB Output is correct
3 Correct 385 ms 76928 KB Output is correct
4 Correct 1235 ms 75780 KB Output is correct
5 Correct 413 ms 75896 KB Output is correct
6 Correct 2854 ms 76844 KB Output is correct
7 Correct 566 ms 76816 KB Output is correct

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 76836 KB Output is correct
2 Execution timed out 3009 ms 77048 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 74356 KB Output is correct
2 Correct 199 ms 74356 KB Output is correct
3 Correct 311 ms 74312 KB Output is correct
4 Correct 722 ms 74368 KB Output is correct
5 Correct 619 ms 74360 KB Output is correct
6 Correct 172 ms 74184 KB Output is correct
7 Correct 981 ms 74412 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 74088 KB Output is correct
2 Correct 67 ms 74184 KB Output is correct
3 Correct 63 ms 74124 KB Output is correct
4 Correct 67 ms 74196 KB Output is correct
5 Correct 84 ms 75360 KB Output is correct
6 Correct 288 ms 76912 KB Output is correct
7 Correct 274 ms 76916 KB Output is correct
8 Correct 385 ms 76928 KB Output is correct
9 Correct 1235 ms 75780 KB Output is correct
10 Correct 413 ms 75896 KB Output is correct
11 Correct 2854 ms 76844 KB Output is correct
12 Correct 566 ms 76816 KB Output is correct
13 Correct 483 ms 76836 KB Output is correct
14 Execution timed out 3009 ms 77048 KB Time limit exceeded
15 Halted 0 ms 0 KB -