Submission #648228

#	Time	Username	Problem	Language	Result	Execution time	Memory
648228		blue	Measures (CEOI22_measures)	C++17	100 / 100	256 ms	35460 KiB

Main

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

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
#define sz(x) int(x.size())

int N, M;
ll D;

const int mx = 200'050;
const ll inf = 1'000'000'000'000'000'00LL;

vi normpos(mx, -1);
vll b(mx);

vpll obj;

struct segtree
{
	int l;
	int r;

	ll zmin = inf;
	ll zmax = -inf;
	ll comb = -inf;

	ll lp = 0; 

	segtree* left = NULL;
	segtree* right = NULL;

	segtree()
	{
		;
	}

	segtree(int L, int R)
	{
		l = L;
		r = R;
		if(l == r)
			return;

		int m = (l+r)/2;
		left = new segtree(l, m);
		right = new segtree(m+1, r);
	}

	void set(int I)
	{
		if(l == r)
		{
			zmin = zmax = lp + (obj[I].first);
			comb = zmax - zmin;
		}
		else
		{
			if(I <= (l+r)/2)
				left->set(I);
			else
				right->set(I);

			zmin = lp + min(left->zmin, right->zmin);
			zmax = lp + max(left->zmax, right->zmax);
			comb = max({left->comb, right->comb, left->zmax - right->zmin});
		}
	}

	void add(int L, int R, ll V)
	{
		if(R < l || r < L)
			return;
		else if(L <= l && r <= R)
		{
			zmin += V;
			zmax += V;
			lp += V;
		}
		else
		{
			left->add(L, R, V);
			right->add(L, R, V);

			zmin = lp + min(left->zmin, right->zmin);
			zmax = lp + max(left->zmax, right->zmax);
			comb = max({left->comb, right->comb, left->zmax - right->zmin});
		}
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> D;
	M += N;

	for(int j = 0; j < M; j++)
	{
		cin >> b[j];
		obj.push_back({b[j], j});
	}

	sort(obj.begin(), obj.end());

	for(int i = 0; i < M; i++)
		normpos[obj[i].second] = i;

	segtree S(0, M-1);

	for(int j = 0; j < M; j++)
	{
		S.set(normpos[j]);
		S.add(normpos[j]+1, M-1, -D);
		ll ans = S.comb;

		if(j >= N)
		{
			cout << ans/2;
			if(ans%2 == 1)
				cout << ".5";
			cout << " ";
		}
	}
	cout << '\n';
}

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