Submission #1313759

#TimeUsernameProblemLanguageResultExecution timeMemory
1313759vlomaczkMeasures (CEOI22_measures)C++20
0 / 100
58 ms30340 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int base = 1<<19;
ll inf = 1e18;
vector<ll> T(2*base,0), mi(2*base,inf), ma(2*base,0); // answer, max value K[x], min value K[x]

void merge(int v, int l, int r) { // Calculates max over i < j of K[j] - K[i] where K[x] = D*x + pos
	T[v] = max(T[l], T[r]);
	T[v] = max(T[v], ma[r] - mi[l]);
	ma[v] = max(ma[r], ma[l]);
	mi[v] = min(mi[r], mi[l]);
}

int D;

void update(int x, int val) {
	x += base;
	mi[x] = ma[x] = D*(x-base) - val;
	x/=2;
	while(x > 0) {
		merge(x,2*x,2*x+1);
		x/=2;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m >> D;
	vector<int> x(n), y(m);
	for(int i=0; i<n; ++i) cin >> x[i];
	for(int i=0; i<m; ++i) cin >> y[i];
	vector<pair<int, int>> pary;
	for(int i=0; i<n; ++i) {
		pary.push_back({x[i], i});
	}
	for(int i=0; i<m; ++i) {
		pary.push_back({y[i], i+n});
	}
	sort(pary.begin(), pary.end());
	int cnt = 0;
	vector<int> idx(n+m);
	for(auto[a,b] : pary) {
		idx[b] = cnt++;
	}	
	for(int i=0; i<n; ++i) update(idx[i], x[i]);
	for(int i=0; i<m; ++i) {
		update(idx[i+n], y[i]);
		if(n==0 && i==0) T[1] = 0;
		cout << T[1]/2;
		if(T[1]%2==1) cout << ".5";
		cout << " ";
	}
	cout << "\n";

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...