oj.uz

Submission #946718

# Submission time Handle Problem Language Result Execution time Memory
946718 2024-03-15T00:10:17 Z MinaRagy06 Measures (CEOI22_measures) C++17
45 / 100
 493 ms 19408 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;
	int cnt, lazy;
	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;
// 		cout << l << ' ' << r << '\n';
		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);
// 		cout << l << ' ' << r << "\n\n";
		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 5 ms 12636 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 5 ms 12776 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 6 ms 12636 KB Output is correct
7 Correct 6 ms 12644 KB Output is correct
8 Correct 5 ms 12632 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 5 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 5 ms 12776 KB Output is correct
5 Correct 5 ms 12636 KB Output is correct
6 Correct 6 ms 12636 KB Output is correct
7 Correct 6 ms 12644 KB Output is correct
8 Correct 5 ms 12632 KB Output is correct
9 Correct 444 ms 16340 KB Output is correct
10 Incorrect 459 ms 16332 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 15304 KB Output is correct
2 Correct 386 ms 19296 KB Output is correct
3 Correct 48 ms 19152 KB Output is correct
4 Correct 418 ms 17424 KB Output is correct
5 Correct 374 ms 18384 KB Output is correct
6 Correct 382 ms 17592 KB Output is correct
7 Correct 373 ms 18508 KB Output is correct
8 Correct 370 ms 17308 KB Output is correct
9 Correct 375 ms 17220 KB Output is correct
10 Correct 373 ms 19408 KB Output is correct
11 Correct 381 ms 17944 KB Output is correct
12 Correct 372 ms 18844 KB Output is correct
13 Correct 371 ms 17116 KB Output is correct
14 Correct 370 ms 19020 KB Output is correct
15 Correct 412 ms 18964 KB Output is correct
16 Correct 404 ms 16868 KB Output is correct
17 Correct 369 ms 18404 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 15304 KB Output is correct
2 Correct 386 ms 19296 KB Output is correct
3 Correct 48 ms 19152 KB Output is correct
4 Correct 418 ms 17424 KB Output is correct
5 Correct 374 ms 18384 KB Output is correct
6 Correct 382 ms 17592 KB Output is correct
7 Correct 373 ms 18508 KB Output is correct
8 Correct 370 ms 17308 KB Output is correct
9 Correct 375 ms 17220 KB Output is correct
10 Correct 373 ms 19408 KB Output is correct
11 Correct 381 ms 17944 KB Output is correct
12 Correct 372 ms 18844 KB Output is correct
13 Correct 371 ms 17116 KB Output is correct
14 Correct 370 ms 19020 KB Output is correct
15 Correct 412 ms 18964 KB Output is correct
16 Correct 404 ms 16868 KB Output is correct
17 Correct 369 ms 18404 KB Output is correct
18 Correct 447 ms 17360 KB Output is correct
19 Incorrect 493 ms 19188 KB Output isn't correct
20 Halted 0 ms 0 KB -