Submission #1243574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243574		sinatbtfard	Measures (CEOI22_measures)	C++20	35 / 100	330 ms	86648 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

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

struct segment {
	int mn[maxn << 2], mx[maxn << 2], lazy[maxn << 2];
	int ans[maxn << 2];
	segment (){
		for (int i = 0; i < (maxn << 2); i++)
			mn[i] = inf, mx[i] = -inf, lazy[i] = 0, ans[i] = -inf;
	}
	void modify (int i, int x){
		mn[i] += x;
		mx[i] += x;
		ans[i] += x;
		lazy[i] += x;
	}
	void shift (int i){
		modify(i << 1, lazy[i]);
		modify((i << 1) ^ 1, lazy[i]);
		lazy[i] = 0;
	}
	void point_update (int i, int L, int R, int ind, int x, int y){
		if (!(R - L)){
			mn[i] = mx[i] = x;
			ans[i] = y;
			return;
		}
		shift(i);
		int mid = (R + L) >> 1;
		if (ind <= mid)
			point_update(i << 1, L, mid, ind, x, y);
		else
			point_update((i << 1) ^ 1, mid + 1, R, ind, x, y);
		mn[i] = min(mn[i << 1], mn[(i << 1) ^ 1]);
		mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
		ans[i] = max(ans[i << 1], ans[(i << 1) ^ 1]);
	}
	void range_update (int i, int L, int R, int l, int r, int x){
		if (L > r || R < l) return;
		if (L >= l && R <= r){
			modify(i, x);
			return;
		}
		shift(i);
		int mid = (R + L) >> 1;
		range_update(i << 1, L, mid, l, r, x);
		range_update((i << 1) ^ 1, mid + 1, R, l, r, x);
		mn[i] = min(mn[i << 1], mn[(i << 1) ^ 1]);
		mx[i] = max(mx[i << 1], mx[(i << 1) ^ 1]);
		ans[i] = max(ans[i << 1], ans[(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];
		shift(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];
		shift(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;

struct segment2 {
	int seg[maxn << 2];
	segment2 (){
		for (int i = 0; i < (maxn << 2); i++)
			seg[i] = 0;
	}
	void update (int i, int L, int R, int ind){
		if (!(R - L)){
			seg[i]++;
			return;
		}
		int mid = (R + L) >> 1;
		if (ind <= mid)
			update(i << 1, L, mid, ind);
		else
			update((i << 1) ^ 1, mid + 1, R, ind);
		seg[i] = seg[i << 1] + seg[(i << 1) ^ 1];
	}
	int get (int i, int L, int R, int l, int r){
		if (L > r || R < l) return 0;
		if (L >= l && R <= r) return seg[i];
		int mid = (R + L) >> 1;
		return get(i << 1, L, mid, l, r) + get((i << 1) ^ 1, mid + 1, R, l, r);
	}
}seg2;

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

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

int jnd[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());
	for (int i = 0; i < n + q; i++){
		jnd[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
		cnt[jnd[i]]++;
		jnd[i] += cnt[jnd[i]];
	}
}

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

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

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