oj.uz

Submission #648228

# Submission time Handle Problem Language Result Execution time Memory
648228 2022-10-05T18:16:10 Z blue Measures (CEOI22_measures) C++17
100 / 100
 256 ms 35460 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2900 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 3 ms 2852 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 3 ms 2948 KB Output is correct
7 Correct 3 ms 2948 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2900 KB Output is correct
2 Correct 2 ms 2900 KB Output is correct
3 Correct 3 ms 2852 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 3 ms 2948 KB Output is correct
7 Correct 3 ms 2948 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 230 ms 32160 KB Output is correct
10 Correct 236 ms 32340 KB Output is correct
11 Correct 105 ms 31664 KB Output is correct
12 Correct 140 ms 32032 KB Output is correct
13 Correct 101 ms 31592 KB Output is correct
14 Correct 128 ms 31640 KB Output is correct
15 Correct 235 ms 31668 KB Output is correct
16 Correct 113 ms 31092 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 32984 KB Output is correct
2 Correct 127 ms 35012 KB Output is correct
3 Correct 133 ms 34760 KB Output is correct
4 Correct 123 ms 32312 KB Output is correct
5 Correct 135 ms 34188 KB Output is correct
6 Correct 117 ms 33208 KB Output is correct
7 Correct 130 ms 34408 KB Output is correct
8 Correct 127 ms 33352 KB Output is correct
9 Correct 117 ms 32828 KB Output is correct
10 Correct 127 ms 35412 KB Output is correct
11 Correct 122 ms 33576 KB Output is correct
12 Correct 130 ms 34560 KB Output is correct
13 Correct 118 ms 32572 KB Output is correct
14 Correct 116 ms 34932 KB Output is correct
15 Correct 130 ms 34528 KB Output is correct
16 Correct 116 ms 32744 KB Output is correct
17 Correct 122 ms 34036 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 32984 KB Output is correct
2 Correct 127 ms 35012 KB Output is correct
3 Correct 133 ms 34760 KB Output is correct
4 Correct 123 ms 32312 KB Output is correct
5 Correct 135 ms 34188 KB Output is correct
6 Correct 117 ms 33208 KB Output is correct
7 Correct 130 ms 34408 KB Output is correct
8 Correct 127 ms 33352 KB Output is correct
9 Correct 117 ms 32828 KB Output is correct
10 Correct 127 ms 35412 KB Output is correct
11 Correct 122 ms 33576 KB Output is correct
12 Correct 130 ms 34560 KB Output is correct
13 Correct 118 ms 32572 KB Output is correct
14 Correct 116 ms 34932 KB Output is correct
15 Correct 130 ms 34528 KB Output is correct
16 Correct 116 ms 32744 KB Output is correct
17 Correct 122 ms 34036 KB Output is correct
18 Correct 238 ms 33720 KB Output is correct
19 Correct 256 ms 34796 KB Output is correct
20 Correct 129 ms 35460 KB Output is correct
21 Correct 154 ms 33312 KB Output is correct
22 Correct 217 ms 33660 KB Output is correct
23 Correct 140 ms 33512 KB Output is correct
24 Correct 251 ms 33856 KB Output is correct
25 Correct 122 ms 33428 KB Output is correct
26 Correct 234 ms 32964 KB Output is correct
27 Correct 239 ms 34908 KB Output is correct
28 Correct 194 ms 33716 KB Output is correct
29 Correct 247 ms 33668 KB Output is correct
30 Correct 152 ms 32444 KB Output is correct
31 Correct 153 ms 34952 KB Output is correct
32 Correct 135 ms 33916 KB Output is correct
33 Correct 246 ms 31808 KB Output is correct
34 Correct 167 ms 33552 KB Output is correct