oj.uz

Submission #696345

# Submission time Handle Problem Language Result Execution time Memory
696345 2023-02-06T09:18:28 Z amirhoseinfar1385 Measures (CEOI22_measures) C++17
100 / 100
 461 ms 34388 KB 
#include<bits/stdc++.h>
using namespace std;

int kaf=(1<<18);
struct segment{
	struct node{
		long long ps,suf,maxa,alla;
		node(){
			ps=suf=maxa=alla=0;
		}
	};
	node seg[(1<<19)];
	void upd(int i){
		if(i==0){
			return;
		}
		if((i<<1)>=(1<<19)){
			return upd((i>>1));
		}
		node nn;
		nn.ps=max(seg[(i<<1)].ps,seg[(i<<1)^1].ps+seg[(i<<1)].alla);
		nn.alla=seg[(i<<1)].alla+seg[(i<<1)^1].alla;
		nn.suf=max(seg[(i<<1)].suf+seg[(i<<1)^1].alla,seg[(i<<1)^1].suf);
		nn.maxa=max(nn.suf,nn.ps);
		nn.maxa=max(nn.maxa,seg[(i<<1)].suf+seg[(i<<1)^1].ps);
		nn.maxa=max(nn.maxa,seg[(i<<1)].maxa);
		nn.maxa=max(nn.maxa,seg[(i<<1)^1].maxa);
		seg[i]=nn;
		upd((i>>1));
	}	
};
segment seg;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m,d;
	cin>>n>>m>>d;
	if(n>0){
		vector<int>allm(n);
		for(int i=0;i<n;i++){
			cin>>allm[i];
		}
		for(int asd=0;asd<m;asd++){
			int ds;
			cin>>ds;
			allm.push_back(ds);
			sort(allm.begin(),allm.end());
			long double res=0;
			long double last=allm[0];
			cout<<setprecision(30);
			for(int i=1;i<(int)allm.size();i++){
				long double dp=last+d;
				if(dp>allm[i]){
					if(abs(dp-allm[i])>res){
						long double fz=abs(dp-allm[i])-res;
						res+=fz/2;
						last=allm[i]+res;
					}
					else{
						last=dp;
					}
				}
				else{
					last=max(dp,allm[i]-res);
				}
	//			cout<<res<<" ";
			}
			cout<<res<<" ";
		}	
		cout<<"\n";
		return 0;
	}
	n=m;
	vector<int>allm(m);
	vector<pair<int,int>>fake(m);
	for(int i=0;i<m;i++){
		cin>>allm[i];
		fake[i]=make_pair(allm[i],i);
	}
	sort(fake.begin(),fake.end());
	vector<int>p(m);
	for(int i=0;i<m;i++){
		p[fake[i].second]=i;
	}
	long double res=0;
	set<int>st;
	st.insert(p[0]);
	set<pair<int,int>>wtf;
	cout<<setprecision(30)<<res<<" ";
	for(int i=1;i<m;i++){
		auto x=st.lower_bound(p[i]);
		if(x!=st.begin()){
			x--;
			auto xp=*x;
			x++;
			seg.seg[kaf+xp].alla=seg.seg[kaf+xp].maxa=seg.seg[kaf+xp].ps=seg.seg[kaf+xp].suf=d-(allm[i]-fake[xp].first);
			seg.upd(kaf+xp);	
		}
		if(x!=st.end()){
			auto xp=*x;
			seg.seg[kaf+p[i]].alla=seg.seg[kaf+p[i]].maxa=seg.seg[kaf+p[i]].ps=seg.seg[kaf+p[i]].suf=d-(fake[xp].first-allm[i]);
			seg.upd(kaf+p[i]);
		}
		long double res=seg.seg[1].maxa;
		res/=2;
		st.insert(p[i]);
		cout<<res<<" ";
	}
	cout<<"\n";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16744 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16700 KB Output is correct
4 Correct 9 ms 16728 KB Output is correct
5 Correct 8 ms 16744 KB Output is correct
6 Correct 8 ms 16748 KB Output is correct
7 Correct 9 ms 16764 KB Output is correct
8 Correct 8 ms 16752 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16744 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16700 KB Output is correct
4 Correct 9 ms 16728 KB Output is correct
5 Correct 8 ms 16744 KB Output is correct
6 Correct 8 ms 16748 KB Output is correct
7 Correct 9 ms 16764 KB Output is correct
8 Correct 8 ms 16752 KB Output is correct
9 Correct 140 ms 20188 KB Output is correct
10 Correct 175 ms 20204 KB Output is correct
11 Correct 77 ms 20196 KB Output is correct
12 Correct 214 ms 20192 KB Output is correct
13 Correct 79 ms 19676 KB Output is correct
14 Correct 122 ms 20172 KB Output is correct
15 Correct 120 ms 19548 KB Output is correct
16 Correct 87 ms 20300 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 30976 KB Output is correct
2 Correct 305 ms 34064 KB Output is correct
3 Correct 284 ms 34108 KB Output is correct
4 Correct 236 ms 32016 KB Output is correct
5 Correct 257 ms 33312 KB Output is correct
6 Correct 247 ms 32252 KB Output is correct
7 Correct 257 ms 33316 KB Output is correct
8 Correct 263 ms 32048 KB Output is correct
9 Correct 240 ms 31968 KB Output is correct
10 Correct 289 ms 34388 KB Output is correct
11 Correct 248 ms 32772 KB Output is correct
12 Correct 269 ms 33688 KB Output is correct
13 Correct 259 ms 31936 KB Output is correct
14 Correct 279 ms 33908 KB Output is correct
15 Correct 303 ms 33860 KB Output is correct
16 Correct 257 ms 31564 KB Output is correct
17 Correct 310 ms 33180 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 30976 KB Output is correct
2 Correct 305 ms 34064 KB Output is correct
3 Correct 284 ms 34108 KB Output is correct
4 Correct 236 ms 32016 KB Output is correct
5 Correct 257 ms 33312 KB Output is correct
6 Correct 247 ms 32252 KB Output is correct
7 Correct 257 ms 33316 KB Output is correct
8 Correct 263 ms 32048 KB Output is correct
9 Correct 240 ms 31968 KB Output is correct
10 Correct 289 ms 34388 KB Output is correct
11 Correct 248 ms 32772 KB Output is correct
12 Correct 269 ms 33688 KB Output is correct
13 Correct 259 ms 31936 KB Output is correct
14 Correct 279 ms 33908 KB Output is correct
15 Correct 303 ms 33860 KB Output is correct
16 Correct 257 ms 31564 KB Output is correct
17 Correct 310 ms 33180 KB Output is correct
18 Correct 417 ms 32272 KB Output is correct
19 Correct 396 ms 34120 KB Output is correct
20 Correct 293 ms 34140 KB Output is correct
21 Correct 251 ms 32052 KB Output is correct
22 Correct 339 ms 32408 KB Output is correct
23 Correct 249 ms 32228 KB Output is correct
24 Correct 426 ms 32728 KB Output is correct
25 Correct 217 ms 31876 KB Output is correct
26 Correct 461 ms 31860 KB Output is correct
27 Correct 440 ms 34384 KB Output is correct
28 Correct 313 ms 32304 KB Output is correct
29 Correct 345 ms 33728 KB Output is correct
30 Correct 254 ms 31824 KB Output is correct
31 Correct 291 ms 33888 KB Output is correct
32 Correct 298 ms 33776 KB Output is correct
33 Correct 371 ms 31552 KB Output is correct
34 Correct 277 ms 33228 KB Output is correct