oj.uz

Submission #719699

# Submission time Handle Problem Language Result Execution time Memory
719699 2023-04-06T13:52:23 Z Arturgo Measures (CEOI22_measures) C++14
100 / 100
 529 ms 22000 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INFINI = 1000 * 1000 * 1000;

int nbInitiaux, nbAjouts, dist;

int ajouts[(1 << 20)];
int mins[(1 << 20)];
int maxs[(1 << 20)];
int deltas[(1 << 20)];

bool est_active[(1 << 20)];

void update(int n) {
	est_active[n] = est_active[2 * n] || est_active[2 * n + 1];
	if(!est_active[n]) return;
	
	maxs[n] = -INFINI + ajouts[n];
	mins[n] = INFINI + ajouts[n];
	if(est_active[2 * n]) {
		mins[n] = min(mins[n], mins[2 * n] + ajouts[n]);
		maxs[n] = max(maxs[n], maxs[2 * n] + ajouts[n]);
	}
	if(est_active[2 * n + 1]) {
		mins[n] = min(mins[n], mins[2 * n + 1] + ajouts[n]);
		maxs[n] = max(maxs[n], maxs[2 * n + 1] + ajouts[n]);
	}
	
	deltas[n] = 0;
	deltas[n] = max(deltas[n], deltas[2 * n]);
	deltas[n] = max(deltas[n], deltas[2 * n + 1]);
	if(est_active[2 * n] && est_active[2 * n + 1])
		deltas[n] = max(deltas[n], maxs[2 * n + 1] - mins[2 * n]);
}

void ajoute(int deb, int fin, int val, int d = 0, int f = (1 << 19), int n = 1) {
	if(f <= deb || fin <= d) return;
	
	if(deb <= d && f <= fin) {
		ajouts[n] += val;
		maxs[n] += val;
		mins[n] += val;
		return;
	} 
	
	int m = (d + f) / 2;
	ajoute(deb, fin, val, d, m, 2 * n);
	ajoute(deb, fin, val, m, f, 2 * n + 1);
	update(n);
}

void active(int deb, int fin, int d = 0, int f = (1 << 19), int n = 1) {
	if(f <= deb || fin <= d) return;
	
	if(deb <= d && f <= fin) {
		est_active[n] = true;
		return;
	} 
	
	int m = (d + f) / 2;
	active(deb, fin, d, m, 2 * n);
	active(deb, fin, m, f, 2 * n + 1);
	update(n);
}

void ajoute_potentiel(int idx, int val) {
	active(idx, idx + 1);
	ajoute(idx, idx + 1, val);
	ajoute(idx + 1, (1 << 19), dist);
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> nbInitiaux >> nbAjouts >> dist;
	
	vector<pair<int, int>> vals;
	
	for(int i = 0;i < nbInitiaux;i++) {
		int pos;
		cin >> pos;
		vals.push_back({pos, -1});
	}
	
	for(int i = 0;i < nbAjouts;i++) {
		int pos;
		cin >> pos;
		vals.push_back({pos, i});
	}
	
	sort(vals.begin(), vals.end());
	
	vector<pair<int, int>> indexes(nbAjouts);
	
	int idx = 0;
	for(pair<int, int> val : vals) {
		if(val.second == -1) {
			int potentiel = -val.first;
			ajoute_potentiel(idx, potentiel);
		}
		else {
			indexes[val.second] = {idx, -val.first};
		}
		idx++;
	}
	
	for(pair<int, int> ajout : indexes) {
		ajoute_potentiel(ajout.first, ajout.second);
		if(deltas[1] % 2 == 1) {
			cout << deltas[1] / 2 << ".5 ";
		}
		else {
			cout << deltas[1] / 2 << " ";
		}
	}
	cout << endl;
	
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 720 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 724 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 720 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 378 ms 15408 KB Output is correct
10 Correct 306 ms 15372 KB Output is correct
11 Correct 262 ms 15396 KB Output is correct
12 Correct 261 ms 15308 KB Output is correct
13 Correct 241 ms 15344 KB Output is correct
14 Correct 323 ms 15412 KB Output is correct
15 Correct 231 ms 15392 KB Output is correct
16 Correct 264 ms 15492 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 19676 KB Output is correct
2 Correct 284 ms 21764 KB Output is correct
3 Correct 308 ms 21688 KB Output is correct
4 Correct 280 ms 19544 KB Output is correct
5 Correct 254 ms 20876 KB Output is correct
6 Correct 298 ms 20076 KB Output is correct
7 Correct 268 ms 20932 KB Output is correct
8 Correct 338 ms 19696 KB Output is correct
9 Correct 372 ms 19568 KB Output is correct
10 Correct 254 ms 22000 KB Output is correct
11 Correct 419 ms 20448 KB Output is correct
12 Correct 356 ms 21380 KB Output is correct
13 Correct 289 ms 19588 KB Output is correct
14 Correct 490 ms 21520 KB Output is correct
15 Correct 323 ms 21336 KB Output is correct
16 Correct 330 ms 19360 KB Output is correct
17 Correct 317 ms 20856 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 19676 KB Output is correct
2 Correct 284 ms 21764 KB Output is correct
3 Correct 308 ms 21688 KB Output is correct
4 Correct 280 ms 19544 KB Output is correct
5 Correct 254 ms 20876 KB Output is correct
6 Correct 298 ms 20076 KB Output is correct
7 Correct 268 ms 20932 KB Output is correct
8 Correct 338 ms 19696 KB Output is correct
9 Correct 372 ms 19568 KB Output is correct
10 Correct 254 ms 22000 KB Output is correct
11 Correct 419 ms 20448 KB Output is correct
12 Correct 356 ms 21380 KB Output is correct
13 Correct 289 ms 19588 KB Output is correct
14 Correct 490 ms 21520 KB Output is correct
15 Correct 323 ms 21336 KB Output is correct
16 Correct 330 ms 19360 KB Output is correct
17 Correct 317 ms 20856 KB Output is correct
18 Correct 452 ms 19936 KB Output is correct
19 Correct 529 ms 21348 KB Output is correct
20 Correct 292 ms 21396 KB Output is correct
21 Correct 424 ms 19376 KB Output is correct
22 Correct 352 ms 19836 KB Output is correct
23 Correct 258 ms 19548 KB Output is correct
24 Correct 394 ms 20232 KB Output is correct
25 Correct 362 ms 19324 KB Output is correct
26 Correct 396 ms 19440 KB Output is correct
27 Correct 428 ms 21740 KB Output is correct
28 Correct 327 ms 19760 KB Output is correct
29 Correct 336 ms 20996 KB Output is correct
30 Correct 311 ms 19204 KB Output is correct
31 Correct 270 ms 21192 KB Output is correct
32 Correct 258 ms 21052 KB Output is correct
33 Correct 381 ms 19276 KB Output is correct
34 Correct 297 ms 20584 KB Output is correct