Submission #719699

#	Time	Username	Problem	Language	Result	Execution time	Memory
719699		Arturgo	Measures (CEOI22_measures)	C++14	100 / 100	529 ms	22000 KiB

Main

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 41 / 41