Submission #996399

#	Time	Username	Problem	Language	Result	Execution time	Memory
996399		0npata	Measures (CEOI22_measures)	C++17	0 / 100	1569 ms	14596 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define vec vector
#define int double

const int INF = 1e17;

struct SegTreeLazy {
	vec<int> data;
	int n;

	SegTreeLazy(int in) {
		int n = 1;
		while(n<in) n*=2;

		data = vec<int>(n);
	}

	void set(int i, int val) {
		data[i] = val;
	}
	int get(int i) {
		return data[i];
	}
	void upd(int l, int r, int val) {
		for(int i = l; i<r; i++) {
			data[i] += val;
		}
	}
};

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m, d;
	cin >> n >> m >> d;

	vec<int> a(n+m+2);
	for(int i = 0; i<n+m; i++) {
		cin >> a[i];
	}
	a[n+m] = INF;
	a[n+m+1] = -INF;

	vec<int> ri(n+m+2);
	iota(ri.begin(), ri.end(), 0);

	sort(ri.begin(), ri.end(), [&] (int i, int j) { return a[i] < a[j]; });
	vec<int> ai(n+m+2);

	for(int i = 0; i<n+m+2; i++) {
		ai[ri[i]] = i;
	}

	multiset<int> ms;
	ms.insert(0);
	ms.insert(n+m+1);

	SegTreeLazy left_shift(n+m+2);
	SegTreeLazy right_shift(n+m+2);

	left_shift.set(0, -INF);
	left_shift.set(n+m+1, INF);
	right_shift.set(0, -INF);
	right_shift.set(n+m+1, INF);

	int topt = 0;

	for(int i = 0; i<n+m; i++) {
		int j = ai[i];

		ms.insert(j);

		auto it = ms.find(j);

		it--;
		int prev = *it;
		it++; it++;
		int nxt = *it;

		int l = left_shift.get(prev);
		int r = right_shift.get(nxt);

		assert(r >= l+d);

		int offs = 2*d-(r-l);

		if(offs >= 0) {
			topt += offs/2;
			left_shift.upd(1, j, -offs/2);
			right_shift.upd(j+1, n+m+1, offs/2);
			r += offs/2;
			l -= offs/2;
		}

		int ml = a[i]-topt;
		int mr = a[i]+topt;

		int mloffs = (r-d)-ml;
		int mroffs = (mr-(l+d));

		offs = min(mloffs, mroffs);

//		cerr << "----------------" << '\n';
//		cerr << "l: " << l << '\n';
//		cerr << "r: " << r << '\n';
//		cerr << "mloffs: " << mloffs << '\n';
//		cerr << "mroffs: " << mroffs << '\n';

		if(offs <= 0) {
			offs = -offs;
			topt += offs/2;
			left_shift.upd(1, j, -offs/2);
			right_shift.upd(j+1, n+m+1, offs/2);
			r += offs/2;
			l -= offs/2;
		}


		int mlpos = max(l+d, a[i]-topt);
		int mrpos = min(r-d, a[i]+topt);

		left_shift.set(j, mlpos);
		right_shift.set(j, mrpos);

		int lr = left_shift.get(nxt);
		int dist = mlpos+d-lr;
		if(dist > 0) {
			left_shift.upd(j+1, n+m+1, dist);
		}

		int rl = right_shift.get(prev);
		dist = rl-(mrpos-d);

		if(dist > 0) {
			right_shift.upd(1, j, -dist);
		}

		if(i >= n) cout << ((double)((int)(topt*2)))/2 << ' ';
	}
	cout << '\n';
}

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