oj.uz

Submission #696090

# Submission time Handle Problem Language Result Execution time Memory
696090 2023-02-05T11:56:50 Z Kahou Measures (CEOI22_measures) C++14
100 / 100
 184 ms 33728 KB 
/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2e5 + 50;
ll n, m, k, d, a[N];
vector<ll> vc;

struct node {
	ll out, pre, suf, cnt;
	node() {
		out = pre = suf = cnt = 0;
	}
} seg[N<<2];

void upd(int id, int u=1, int tl=1, int tr=k) {
	if (tl == tr) {
		seg[u].cnt++;
		seg[u].pre = seg[u].cnt*d;
		seg[u].suf = seg[u].cnt*d;
		seg[u].out = (seg[u].cnt-1)*d;
		return;
	}
	int md = (tl+tr)>>1;
	int lc = u<<1;
	int rc = u<<1|1;
	if (id <= md) upd(id, lc, tl, md);
	else upd(id, rc, md+1, tr);
	
	seg[u].out = max(max(seg[lc].out, seg[rc].out), seg[lc].suf+seg[rc].pre-(vc[md+1]-vc[md])-d);
	seg[u].cnt = seg[lc].cnt + seg[rc].cnt;
	seg[u].pre = max(seg[lc].pre, seg[rc].pre-(vc[md+1]-vc[tl])+d*seg[lc].cnt);
	seg[u].suf = max(seg[rc].suf, seg[lc].suf-(vc[tr]-vc[md])+d*seg[rc].cnt);
}

void solve() {
	cin >> n >> m >> d;
	for (int i = 1; i <= n+m; i++) {
		cin >> a[i];
		vc.push_back(a[i]);
	}
	vc.push_back(0);
	sort(vc.begin(), vc.end());
	vc.resize(unique(vc.begin(), vc.end())-vc.begin());
	k = vc.size()-1;
	for (int i = 1; i <= n+m; i++) {
		int id = lower_bound(vc.begin(), vc.end(), a[i])-vc.begin();
		upd(id);
		if (i > n) {
			cout << seg[1].out/2;
			if (seg[1].out&1) cout << ".5";
			cout << ' ';
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25380 KB Output is correct
2 Correct 11 ms 25428 KB Output is correct
3 Correct 14 ms 25420 KB Output is correct
4 Correct 11 ms 25432 KB Output is correct
5 Correct 11 ms 25416 KB Output is correct
6 Correct 11 ms 25428 KB Output is correct
7 Correct 12 ms 25428 KB Output is correct
8 Correct 13 ms 25428 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25380 KB Output is correct
2 Correct 11 ms 25428 KB Output is correct
3 Correct 14 ms 25420 KB Output is correct
4 Correct 11 ms 25432 KB Output is correct
5 Correct 11 ms 25416 KB Output is correct
6 Correct 11 ms 25428 KB Output is correct
7 Correct 12 ms 25428 KB Output is correct
8 Correct 13 ms 25428 KB Output is correct
9 Correct 151 ms 30544 KB Output is correct
10 Correct 157 ms 30480 KB Output is correct
11 Correct 36 ms 30580 KB Output is correct
12 Correct 113 ms 30540 KB Output is correct
13 Correct 84 ms 29984 KB Output is correct
14 Correct 82 ms 30516 KB Output is correct
15 Correct 159 ms 29840 KB Output is correct
16 Correct 91 ms 30528 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 30144 KB Output is correct
2 Correct 109 ms 33492 KB Output is correct
3 Correct 53 ms 33432 KB Output is correct
4 Correct 114 ms 31284 KB Output is correct
5 Correct 113 ms 32628 KB Output is correct
6 Correct 115 ms 31636 KB Output is correct
7 Correct 121 ms 32620 KB Output is correct
8 Correct 105 ms 31316 KB Output is correct
9 Correct 106 ms 31328 KB Output is correct
10 Correct 111 ms 33728 KB Output is correct
11 Correct 122 ms 32160 KB Output is correct
12 Correct 110 ms 33080 KB Output is correct
13 Correct 110 ms 31348 KB Output is correct
14 Correct 112 ms 33228 KB Output is correct
15 Correct 109 ms 33068 KB Output is correct
16 Correct 114 ms 30912 KB Output is correct
17 Correct 113 ms 32536 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 30144 KB Output is correct
2 Correct 109 ms 33492 KB Output is correct
3 Correct 53 ms 33432 KB Output is correct
4 Correct 114 ms 31284 KB Output is correct
5 Correct 113 ms 32628 KB Output is correct
6 Correct 115 ms 31636 KB Output is correct
7 Correct 121 ms 32620 KB Output is correct
8 Correct 105 ms 31316 KB Output is correct
9 Correct 106 ms 31328 KB Output is correct
10 Correct 111 ms 33728 KB Output is correct
11 Correct 122 ms 32160 KB Output is correct
12 Correct 110 ms 33080 KB Output is correct
13 Correct 110 ms 31348 KB Output is correct
14 Correct 112 ms 33228 KB Output is correct
15 Correct 109 ms 33068 KB Output is correct
16 Correct 114 ms 30912 KB Output is correct
17 Correct 113 ms 32536 KB Output is correct
18 Correct 181 ms 31724 KB Output is correct
19 Correct 184 ms 33396 KB Output is correct
20 Correct 57 ms 33408 KB Output is correct
21 Correct 135 ms 31380 KB Output is correct
22 Correct 140 ms 31724 KB Output is correct
23 Correct 101 ms 31600 KB Output is correct
24 Correct 166 ms 32308 KB Output is correct
25 Correct 106 ms 31232 KB Output is correct
26 Correct 171 ms 31252 KB Output is correct
27 Correct 175 ms 33692 KB Output is correct
28 Correct 158 ms 31708 KB Output is correct
29 Correct 156 ms 33040 KB Output is correct
30 Correct 123 ms 31204 KB Output is correct
31 Correct 135 ms 33272 KB Output is correct
32 Correct 117 ms 33128 KB Output is correct
33 Correct 160 ms 30856 KB Output is correct
34 Correct 130 ms 32660 KB Output is correct