oj.uz

Submission #1105225

# Submission time Handle Problem Language Result Execution time Memory
1105225 2024-10-25T18:45:34 Z vako_p Measures (CEOI22_measures) C++14
100 / 100
 397 ms 50248 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 1e6 + 5;
ll n,a[mxN],b[mxN],d,n1,m,idx[mxN];
map<ll,ll> idx1;
set<ll> ss;

struct segtree{
	vector<ll> v,p,s,cnt;	
	ll sz = 1;
	
	void init(){
		while(sz < n) sz *= 2;
		v.assign(2 * sz, 0LL);
		p.assign(2 * sz, -1e10);
		s.assign(2 * sz, -1e10);
		cnt.assign(2 * sz, 0LL);
	}
	
	void set(ll i, ll x, ll lx, ll rx){
		if(rx - lx == 1){
			s[x] = -idx[min(i + 1, n - 1)] + idx[i] + cnt[x] * d;
			p[x] = cnt[x] * d; 
			v[x] = cnt[x] * d;
			cnt[x]++;
//			if(i == 2) cout << i << ' ' << lx << ' ' << rx << "---> " << p[x] << ' ' << s[x] << " : " << v[x] << '\n';
			return;
		}
		ll mid = lx + (rx - lx) / 2;
		if(i < mid) set(i, 2 * x + 1, lx, mid);
		else set(i, 2 * x + 2, mid, rx);
		cnt[x] = cnt[2 * x + 1] + cnt[2 * x + 2];
		v[x] = max(v[2 * x + 1] , v[2 * x + 2]);
		s[x] = s[2 * x + 2];
		p[x] = p[2 * x + 1];
		if(cnt[2 * x + 1] and cnt[2 * x + 2]) v[x] = max(v[x], d + s[2 * x + 1] + p[2 * x + 2]);
		p[x] = max(p[x], p[2 * x + 2] - (idx[mid] - idx[lx]) + cnt[2 * x + 1] * d);
		s[x] = max(s[x], s[2 * x + 1] - (idx[min(rx, n - 1)] - idx[mid]) + cnt[2 * x + 2] * d);
//		if(i == 2) cout << i << ' ' << lx << ' ' << rx << "---> " << p[x] << ' ' << s[x] << " : " << v[x] << '\n';
	}
	
	void set(ll i){
		set(i, 0, 0, sz);
	}
	
	ll find(){
		return v[0]; 
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n1 >> m >> d;
	for(int i = 0; i < n1; i++){
		cin >> a[i];
		ss.insert(a[i]);
	}
	for(int i = 0; i < m; i++){
		cin >> b[i];
		ss.insert(b[i]);
	}
	ll cc = 0;
	for(auto it : ss){
		idx1[it] = cc;
		idx[cc++] = it;
	}
//	idx[cc] = 2e9;
	n = ss.size();
	segtree s;
	s.init();
	
	for(int i = 0; i < n1; i++){
		s.set(idx1[a[i]]);
//		cout << a[i] << ' ' << idx1[a[i]] << ' ' << s.find() << '\n'; 	
	}
	for(int i = 0; i < m; i++){
		s.set(idx1[b[i]]);
		ll ans = s.find();
		cout << ans / 2;
		if(ans % 2) cout << ".5 ";
		else cout << ' ';
	}
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 2 ms 4688 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2 ms 4688 KB Output is correct
5 Correct 2 ms 4688 KB Output is correct
6 Correct 2 ms 4688 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 ms 4688 KB Output is correct
9 Correct 360 ms 47176 KB Output is correct
10 Correct 349 ms 49040 KB Output is correct
11 Correct 18 ms 8528 KB Output is correct
12 Correct 211 ms 48968 KB Output is correct
13 Correct 183 ms 48456 KB Output is correct
14 Correct 180 ms 48968 KB Output is correct
15 Correct 334 ms 48456 KB Output is correct
16 Correct 191 ms 48968 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 46160 KB Output is correct
2 Correct 224 ms 48036 KB Output is correct
3 Correct 39 ms 9288 KB Output is correct
4 Correct 184 ms 47688 KB Output is correct
5 Correct 184 ms 48968 KB Output is correct
6 Correct 189 ms 48200 KB Output is correct
7 Correct 178 ms 49080 KB Output is correct
8 Correct 186 ms 47944 KB Output is correct
9 Correct 193 ms 47688 KB Output is correct
10 Correct 181 ms 50248 KB Output is correct
11 Correct 182 ms 48456 KB Output is correct
12 Correct 179 ms 49480 KB Output is correct
13 Correct 197 ms 47432 KB Output is correct
14 Correct 201 ms 49736 KB Output is correct
15 Correct 200 ms 48968 KB Output is correct
16 Correct 197 ms 47124 KB Output is correct
17 Correct 205 ms 48972 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 46160 KB Output is correct
2 Correct 224 ms 48036 KB Output is correct
3 Correct 39 ms 9288 KB Output is correct
4 Correct 184 ms 47688 KB Output is correct
5 Correct 184 ms 48968 KB Output is correct
6 Correct 189 ms 48200 KB Output is correct
7 Correct 178 ms 49080 KB Output is correct
8 Correct 186 ms 47944 KB Output is correct
9 Correct 193 ms 47688 KB Output is correct
10 Correct 181 ms 50248 KB Output is correct
11 Correct 182 ms 48456 KB Output is correct
12 Correct 179 ms 49480 KB Output is correct
13 Correct 197 ms 47432 KB Output is correct
14 Correct 201 ms 49736 KB Output is correct
15 Correct 200 ms 48968 KB Output is correct
16 Correct 197 ms 47124 KB Output is correct
17 Correct 205 ms 48972 KB Output is correct
18 Correct 388 ms 47944 KB Output is correct
19 Correct 373 ms 49736 KB Output is correct
20 Correct 30 ms 9288 KB Output is correct
21 Correct 221 ms 47944 KB Output is correct
22 Correct 332 ms 48200 KB Output is correct
23 Correct 199 ms 47944 KB Output is correct
24 Correct 397 ms 48712 KB Output is correct
25 Correct 196 ms 47688 KB Output is correct
26 Correct 351 ms 48004 KB Output is correct
27 Correct 325 ms 50248 KB Output is correct
28 Correct 275 ms 48200 KB Output is correct
29 Correct 344 ms 49480 KB Output is correct
30 Correct 224 ms 47688 KB Output is correct
31 Correct 212 ms 49692 KB Output is correct
32 Correct 186 ms 49480 KB Output is correct
33 Correct 305 ms 47432 KB Output is correct
34 Correct 208 ms 48968 KB Output is correct