Submission #787421

#	Time	Username	Problem	Language	Result	Execution time	Memory
787421		ymm	Measures (CEOI22_measures)	C++17	0 / 100	150 ms	44344 KiB

Main

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 200'020;
ll a[N], b[N], D;
int n, m;
vector<pll> cmper;

namespace seg {
	struct {
		ll mn, mx, cst;
		int cnt;
	} t[N*4];
	int sz;

	void mv(__typeof__(*t) &v, ll x) {
		ll mochale = (v.mx - v.mn) - (v.cnt-1)*D;
		v.mn += x;
		v.mx += x;
		v.cst += abs(x);
		if (x > 0)
			v.mx -= min(mochale, abs(2*x));
		else
			v.mn += min(mochale, abs(2*x));
	}

	void merge(int i) {
		if (t[2*i+1].cst == -1) {
			t[i] = t[2*i+2];
			return;
		}
		if (t[2*i+2].cst == -1) {
			t[i] = t[2*i+1];
			return;
		}
		auto l = t[2*i+1];
		auto r = t[2*i+2];
		if (l.cst < r.cst) {
			ll x = r.mn - D - l.mx;
			if (abs(x) > r.cst - l.cst) {
				auto tmp = r.cst - l.cst;
				if (x < 0)
					tmp = -tmp;
				x = tmp;
			}
			mv(l, x);
		}
		if (r.cst < l.cst) {
			ll x = l.mx + D - r.mn;
			if (abs(x) > l.cst - r.cst) {
				auto tmp = l.cst - r.cst;
				if (x < 0)
					tmp = -tmp;
				x = tmp;
			}
			mv(r, x);
		}
		t[i].cst = max(l.cst, r.cst);
		if (r.mn - l.mx < D) {
			ll x = D - (r.mn - l.mx);
			assert(x%2 == 0);
			x /= 2;
			mv(r, x);
			mv(l, -x);
			t[i].cst += x;
		}
		t[i].mn = l.mn;
		t[i].mx = r.mx;
		t[i].cnt = l.cnt + r.cnt;
	}

	void init(int n) {
		sz = n;
		fill(t, t+4*sz, __typeof__(*t){ -1, -1, -1, -1});
	}

	void up(int p, ll x, int i, int b, int e) {
		if (e-b == 1) {
			t[i] = { .mn = x, .mx = x, .cst = 0, .cnt = 1 };
			return;
		}
		if (p < (b+e)/2)
			up(p, x, 2*i+1, b, (b+e)/2);
		else
			up(p, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void up(int p, ll x) { up(p, x, 0, 0, sz); }
}

multiset<ll> S;

bool naive(ll k)
{
	ll lst = -1e18;
	for (ll x : S) {
		ll p = max(x - k, lst + D);
		if (p - x > k)
			return 0;
		lst = p;
	}
	return 1;
}
ll bin() {
	ll l = 0, r = 1e18;
	while (l < r) {
		ll m = (l+r)/2;
		if (naive(m))
			r = m;
		else
			l = m+1;
	}
	return l;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m >> D;
	D *= 2;
	Loop (i,0,n) {
		cin >> a[i];
		a[i] *= 2;
		cmper.push_back({a[i], i});
	}
	srand(time(0));
	Loop (i,0,m) {
		//b[i]=rand()%100;
		cin >> b[i];
		//cout << b[i] << ' ';
		b[i] *= 2;
		cmper.push_back({b[i], i+n});
	}
	//cout << '\n';
	sort(cmper.begin(), cmper.end());
	seg::init(n + m);
	Loop (i,0,n) {
		int pos = lower_bound(cmper.begin(), cmper.end(), pll{a[i], i}) - cmper.begin();
		seg::up(pos, a[i]);
		S.insert(a[i]);
	}
	Loop (i,0,m) {
		int pos = lower_bound(cmper.begin(), cmper.end(), pll{b[i], i+n}) - cmper.begin();
		seg::up(pos, b[i]);
		S.insert(b[i]);
		ll x = seg::t[0].cst;
		cout << x/2;
		if (x%2)
			cout << ".5";
		cout << ' ';
		//cout << double(bin())/2 << '\n';
		//cout.flush();
		//assert(bin() == x);
	}
	cout << '\n';
}

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