Submission #1243532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243532		sinatbtfard	Measures (CEOI22_measures)	C++20	10 / 100	129 ms	39320 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int maxn = 5e5 + 10, inf = 1e15;

struct segment {
	int mn[maxn << 2], mx[maxn << 2];
	segment (){
		for (int i = 0; i < (maxn << 2); i++)
			mn[i] = inf, mx[i] = -inf;
	}
	void update (int i, int L, int R, int ind, int x){
		if (!(R - L)){
			mn[i] = mx[i] = x;
			return;
		}
		int mid = (R + L) >> 1;
		if (ind <= mid)
			update(i << 1, L, mid, ind, x);
		else
			update((i << 1) ^ 1, mid + 1, R, ind, x);
		mn[i] = min(mn[i << 1], mn[(i << 1) ^ 1]);
		mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
	}
	int getmn (int i, int L, int R, int l, int r){
		if (L > r || R < l) return inf;
		if (L >= l && R <= r) return mn[i];
		int mid = (R + L) >> 1;
		return min(getmn(i << 1, L, mid, l, r), getmn((i << 1) ^ 1, mid + 1, R, l, r));
	}
	int getmx (int i, int L, int R, int l, int r){
		if (L > r || R < l) return -inf;
		if (L >= l && R <= r) return mx[i];
		int mid = (R + L) >> 1;
		return max(getmx(i << 1, L, mid, l, r), getmx((i << 1) ^ 1, mid + 1, R, l, r));
	}
}seg;

int n, q, d, a[maxn];

void read (){
	cin >> n >> q >> d;
	for (int i = 0; i < n + q; i++)
		cin >> a[i];
}

int ind[maxn], cnt[maxn];

void compress (){
	vector <int> val;
	for (int i = 0; i < n + q; i++)
		val.push_back(a[i]);
	sort(val.begin(), val.end());
	val.resize(unique(val.begin(), val.end()) - val.begin());
	for (int i = 0; i < n + q; i++){
		ind[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
		cnt[ind[i]]++;
		ind[i] += cnt[ind[i]];
	}
}

void solve (){
	compress();
	int ans = 0;
	for (int i = 0; i < n + q; i++){
		int x = ind[i] * d - a[i];
		seg.update(1, 0, maxn - 1, ind[i], x);
		int r0 = x - seg.getmn(1, 0, maxn - 1, 0, ind[i] - 1);
		int r1 = seg.getmx(1, 0, maxn - 1, ind[i] + 1, maxn - 1) - x;
		ans = max({ans, r0, r1});
		if (i >= n){
			cout << ans / 2;
			if (ans & 1) cout << ".5";
			cout << " ";
		}
	}
}

int32_t main (){
	ios_base::sync_with_stdio(0), cin.tie(0);
	read();
	solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 35
• Subtask 4: 0 / 41