oj.uz

Submission #946719

# Submission time Handle Problem Language Result Execution time Memory
946719 2024-03-15T00:21:20 Z MinaRagy06 Measures (CEOI22_measures) C++17
100 / 100
 486 ms 23748 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)
#define SZ(x) (int) x.size()

struct node {
	ll pos, neg, lazy;
	int cnt;
	node(ll x) {
		pos = x;
		neg = -x;
		cnt = 1;
		lazy = 0;
	}
	node() {pos = neg = -1e18; cnt = lazy = 0;}
	friend node operator+(const node &l, const node &r) {
		node ret;
		ret.pos = max(l.pos, r.pos);
		ret.neg = max(l.neg, r.neg);
		ret.cnt = l.cnt + r.cnt;
		return ret;
	}
} seg[1 << 19];
void process(int i, int l, int r) {
	if (l != r) {
		for (auto c : {i << 1, i << 1 | 1}) {
			seg[c].lazy += seg[i].lazy;
		}
	}
	seg[i].pos += seg[i].lazy;
	seg[i].neg -= seg[i].lazy;
	seg[i].lazy = 0;
}
void add(int i, int l, int r, int s, int e, ll v) {
	process(i, l, r);
	if (s <= l && r <= e) {
		seg[i].lazy += v;
		process(i, l, r);
		return;
	}
	if (r < s || e < l) {
		return;
	}
	add(i << 1, l, md, s, e, v);
	add(i << 1 | 1, md + 1, r, s, e, v);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
ll mx = -1e18;
ll d;
void upd(int i, int l, int r, int x, ll v, ll pos) {
	process(i, l, r);
	if (r < x || x < l) {
		return;
	}
	if (l == r) {
		seg[i].pos = max(seg[i].pos, d * pos - v);
		seg[i].neg = max(seg[i].neg, -(d * pos - v));
		mx = max(mx, seg[i].pos + seg[i].neg);
		seg[i].cnt++;
		return;
	}
	upd(i << 1, l, md, x, v, pos);
	upd(i << 1 | 1, md + 1, r, x, v, pos + seg[i << 1].cnt);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
	process(i, l, r);
	if (s <= l && r <= e) {
		return seg[i];
	}
	if (r < s || e < l) {
		return node();
	}
	return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m >> d;
	int a[n], b[m];
	vector<int> v;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		v.push_back(a[i]);
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
		v.push_back(b[i]);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	auto insert = [&] (int x) {
		int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
		add(1, 0, v.size() - 1, pos, v.size() - 1, d);
		upd(1, 0, v.size() - 1, pos, x, 0);
		ll l = get(1, 0, v.size() - 1, 0, pos - 1).neg;
		ll r = get(1, 0, v.size() - 1, pos, v.size() - 1).pos;
		mx = max(mx, l + r);
		l = get(1, 0, v.size() - 1, 0, pos).neg;
		r = get(1, 0, v.size() - 1, pos + 1, v.size() - 1).pos;
		mx = max(mx, l + r);
		return mx;
	};
	for (int i = 0; i < n; i++) {
		mx = max(mx, insert(a[i]));
	}
	for (int i = 0; i < m; i++) {
		mx = max(mx, insert(b[i]));
		ll v = max(mx, 0ll);
		if (v & 1) {
			cout << v / 2 << ".5 ";
		} else {
			cout << v / 2 << ' ';
		}
	}
	cout << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 7 ms 16732 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Correct 6 ms 16732 KB Output is correct
8 Correct 5 ms 16732 KB Output is correct
9 Correct 450 ms 18908 KB Output is correct
10 Correct 420 ms 18652 KB Output is correct
11 Correct 32 ms 20504 KB Output is correct
12 Correct 430 ms 20432 KB Output is correct
13 Correct 354 ms 19920 KB Output is correct
14 Correct 356 ms 20440 KB Output is correct
15 Correct 486 ms 19992 KB Output is correct
16 Correct 352 ms 20440 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 19476 KB Output is correct
2 Correct 363 ms 21448 KB Output is correct
3 Correct 48 ms 21440 KB Output is correct
4 Correct 356 ms 19160 KB Output is correct
5 Correct 364 ms 20988 KB Output is correct
6 Correct 358 ms 19636 KB Output is correct
7 Correct 373 ms 20704 KB Output is correct
8 Correct 356 ms 19424 KB Output is correct
9 Correct 368 ms 19376 KB Output is correct
10 Correct 364 ms 21708 KB Output is correct
11 Correct 372 ms 20064 KB Output is correct
12 Correct 365 ms 20940 KB Output is correct
13 Correct 361 ms 19116 KB Output is correct
14 Correct 375 ms 21528 KB Output is correct
15 Correct 405 ms 21136 KB Output is correct
16 Correct 371 ms 19648 KB Output is correct
17 Correct 365 ms 20424 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 19476 KB Output is correct
2 Correct 363 ms 21448 KB Output is correct
3 Correct 48 ms 21440 KB Output is correct
4 Correct 356 ms 19160 KB Output is correct
5 Correct 364 ms 20988 KB Output is correct
6 Correct 358 ms 19636 KB Output is correct
7 Correct 373 ms 20704 KB Output is correct
8 Correct 356 ms 19424 KB Output is correct
9 Correct 368 ms 19376 KB Output is correct
10 Correct 364 ms 21708 KB Output is correct
11 Correct 372 ms 20064 KB Output is correct
12 Correct 365 ms 20940 KB Output is correct
13 Correct 361 ms 19116 KB Output is correct
14 Correct 375 ms 21528 KB Output is correct
15 Correct 405 ms 21136 KB Output is correct
16 Correct 371 ms 19648 KB Output is correct
17 Correct 365 ms 20424 KB Output is correct
18 Correct 453 ms 19660 KB Output is correct
19 Correct 479 ms 21176 KB Output is correct
20 Correct 46 ms 23204 KB Output is correct
21 Correct 420 ms 21272 KB Output is correct
22 Correct 401 ms 21712 KB Output is correct
23 Correct 382 ms 21504 KB Output is correct
24 Correct 463 ms 22336 KB Output is correct
25 Correct 375 ms 21200 KB Output is correct
26 Correct 455 ms 21240 KB Output is correct
27 Correct 457 ms 23748 KB Output is correct
28 Correct 401 ms 21484 KB Output is correct
29 Correct 433 ms 22904 KB Output is correct
30 Correct 400 ms 21200 KB Output is correct
31 Correct 404 ms 23072 KB Output is correct
32 Correct 417 ms 23000 KB Output is correct
33 Correct 455 ms 20624 KB Output is correct
34 Correct 404 ms 22524 KB Output is correct