oj.uz

Submission #724080

# Submission time Handle Problem Language Result Execution time Memory
724080 2023-04-14T17:07:39 Z stage Measures (CEOI22_measures) C++14
100 / 100
 328 ms 33248 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node{
	int max,min,ans;
};

const int N = 2e5, inf = 1e17;

node segt[4*N+5];
int lazy[4*N+5];

node merge(node a, node b){
	node c;
	c.ans = max({a.ans,b.ans,a.max-b.min});
	c.max = max(a.max,b.max);
	c.min = min(a.min,b.min);
	return c;
}

void update(int idx, int l, int r, int L, int R, int val){
	if (l > R or r < L) return;
	if (l >= L and r <= R){
		if (L == R) segt[idx] = {val+lazy[idx],val+lazy[idx],0};
		else{
			segt[idx].max += val;
			segt[idx].min += val;
			lazy[idx] += val;
		}
		return;
	}
	for (int k:{2*idx,2*idx+1}){
		segt[k].min += lazy[idx];
		segt[k].max += lazy[idx];
		lazy[k] += lazy[idx];
	}
	lazy[idx] = 0;
	int mid = (l+r)/2;
	update(2*idx,l,mid,L,R,val);
	update(2*idx+1,mid+1,r,L,R,val);
	segt[idx] = merge(segt[2*idx],segt[2*idx+1]);
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,d;
	cin >> n >> m >> d;
	fill_n(segt,4*N+5,node{-inf,inf,-inf});
	vector<int> init(n+m), to(n+m);
	vector<pair<int,int>> a(n+m); 
	for (int i=0; i<n+m; ++i){
		cin >> init[i];
		a[i] = {init[i],i};
	}
	sort(a.begin(),a.end());
	for (int i=0; i<n+m; ++i) to[a[i].second] = i;
	for (int i=0; i<n+m; ++i){
		int pos = to[i];
		update(1,0,n+m+4,pos,pos,init[i]);
		update(1,0,n+m+4,pos+1,n+m+4,-d);
		if (i >= n){
			int ans = segt[1].ans;
			cout << ans/2;
			if (ans&1) cout << ".5";
			cout << ' ';
		}
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19156 KB Output is correct
3 Correct 9 ms 19152 KB Output is correct
4 Correct 13 ms 19184 KB Output is correct
5 Correct 10 ms 19228 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 12 ms 19172 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 10 ms 19156 KB Output is correct
3 Correct 9 ms 19152 KB Output is correct
4 Correct 13 ms 19184 KB Output is correct
5 Correct 10 ms 19228 KB Output is correct
6 Correct 11 ms 19156 KB Output is correct
7 Correct 11 ms 19156 KB Output is correct
8 Correct 12 ms 19172 KB Output is correct
9 Correct 277 ms 30000 KB Output is correct
10 Correct 282 ms 30132 KB Output is correct
11 Correct 193 ms 30088 KB Output is correct
12 Correct 216 ms 30136 KB Output is correct
13 Correct 203 ms 30028 KB Output is correct
14 Correct 194 ms 30044 KB Output is correct
15 Correct 270 ms 30124 KB Output is correct
16 Correct 212 ms 30148 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 30544 KB Output is correct
2 Correct 233 ms 32968 KB Output is correct
3 Correct 225 ms 32952 KB Output is correct
4 Correct 199 ms 30792 KB Output is correct
5 Correct 201 ms 32128 KB Output is correct
6 Correct 211 ms 31200 KB Output is correct
7 Correct 207 ms 32372 KB Output is correct
8 Correct 211 ms 30876 KB Output is correct
9 Correct 212 ms 30892 KB Output is correct
10 Correct 213 ms 33248 KB Output is correct
11 Correct 230 ms 31732 KB Output is correct
12 Correct 204 ms 32672 KB Output is correct
13 Correct 210 ms 30924 KB Output is correct
14 Correct 202 ms 32816 KB Output is correct
15 Correct 229 ms 32696 KB Output is correct
16 Correct 211 ms 30804 KB Output is correct
17 Correct 226 ms 32148 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 30544 KB Output is correct
2 Correct 233 ms 32968 KB Output is correct
3 Correct 225 ms 32952 KB Output is correct
4 Correct 199 ms 30792 KB Output is correct
5 Correct 201 ms 32128 KB Output is correct
6 Correct 211 ms 31200 KB Output is correct
7 Correct 207 ms 32372 KB Output is correct
8 Correct 211 ms 30876 KB Output is correct
9 Correct 212 ms 30892 KB Output is correct
10 Correct 213 ms 33248 KB Output is correct
11 Correct 230 ms 31732 KB Output is correct
12 Correct 204 ms 32672 KB Output is correct
13 Correct 210 ms 30924 KB Output is correct
14 Correct 202 ms 32816 KB Output is correct
15 Correct 229 ms 32696 KB Output is correct
16 Correct 211 ms 30804 KB Output is correct
17 Correct 226 ms 32148 KB Output is correct
18 Correct 270 ms 31268 KB Output is correct
19 Correct 308 ms 32896 KB Output is correct
20 Correct 225 ms 33084 KB Output is correct
21 Correct 247 ms 30896 KB Output is correct
22 Correct 244 ms 31424 KB Output is correct
23 Correct 226 ms 31012 KB Output is correct
24 Correct 266 ms 31548 KB Output is correct
25 Correct 224 ms 30700 KB Output is correct
26 Correct 288 ms 30744 KB Output is correct
27 Correct 328 ms 33232 KB Output is correct
28 Correct 245 ms 31292 KB Output is correct
29 Correct 293 ms 32632 KB Output is correct
30 Correct 239 ms 30632 KB Output is correct
31 Correct 259 ms 32932 KB Output is correct
32 Correct 230 ms 32540 KB Output is correct
33 Correct 280 ms 30760 KB Output is correct
34 Correct 238 ms 32048 KB Output is correct