oj.uz

Submission #696191

# Submission time Handle Problem Language Result Execution time Memory
696191 2023-02-05T18:55:41 Z amirhoseinfar1385 Measures (CEOI22_measures) C++17
59 / 100
 586 ms 22592 KB 
#include<bits/stdc++.h>
using namespace std;

int kaf=(1<<18);
struct segment{
	long double seg[(1<<19)];
	void upd(int i,int l,int r,int tl,int tr,long double w){
		if(l>r||l>tr||r<tl){
			//cout<<"fst "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<w<<"\n";
			return ;
		}
		if(l>=tl&&r<=tr){
			//cout<<"fst "<<l<<" "<<r<<" "<<w<<"\n";
			seg[i]+=w;
			return ;
		}
		int m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
	}
	long double pors(int i){
		if(i==0){
			return 0;
		}
		long double d=seg[i]+pors((i>>1));
		return d;
	}
};
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]);
	seg.upd(1,0,kaf-1,p[0],p[0],allm[0]);
	cout<<setprecision(30)<<res<<" ";
	for(int i=1;i<m;i++){
		auto x=st.lower_bound(p[i]);
		long double wtf=seg.pors(kaf+p[i]);
		seg.upd(1,0,kaf-1,p[i],p[i],allm[i]-wtf);
		long double fres=res;
		if(x!=st.begin()){
			x--;
			auto xp=*x;
			x++;
			long double z=seg.pors(kaf+xp);
			long double dp=z+d;
			//cout<<allm[i]<<" "<<dp<<" "<<z<<" "<<xp<<"\n";
			if(dp>allm[i]){
				if(dp-allm[i]>res){
					long double fz=dp-allm[i]-res;
					long double tagh=fz/2;
					//cout<<"what "<<p[i]<<" "<<tagh<<" "<<fz<<"\n";
					seg.upd(1,0,kaf-1,0,p[i]-1,-tagh);
					seg.upd(1,0,kaf-1,p[i],p[i],tagh+res);
					res+=fz/2;
				}
				else{
					long double tagh=dp-allm[i];
					seg.upd(1,0,kaf-1,p[i],p[i],tagh); 
				}
			}
			else{
				long double tagh=min(res,allm[i]-dp);
				seg.upd(1,0,kaf-1,p[i],p[i],-tagh);
			}
		}
		fres=res-fres;
		if(x!=st.end()){
			auto xp=*x;
			long double z=seg.pors(kaf+p[i]);
			long double dp=z+d;
			long double ft=seg.pors(kaf+xp);
			//cout<<ft<<" "<<dp<<" "<<z<<" "<<xp<<"\n";
			if(dp>ft){
				if(dp-ft>fres){
					long double fz=dp-ft-fres;
					long double tagh=fz/2;
					//cout<<"ehat "<<tagh<<" "<<fz<<" "<<xp<<" "<<fres<<" "<<p[i]<<"\n";
					seg.upd(1,0,kaf-1,0,p[i],-tagh);
					seg.upd(1,0,kaf-1,xp,n,tagh+fres);
					res+=fz/2;
				}
				else{
					long double tagh=dp-ft;
					seg.upd(1,0,kaf-1,xp,n,tagh);
				}
			}
			else{
				long double tagh=min(fres,ft-dp);
				seg.upd(1,0,kaf-1,xp,n,-tagh);
			}
		}
		st.insert(p[i]);
		cout<<res<<" ";
	}
	cout<<"\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 112 ms 1876 KB Output is correct
10 Correct 170 ms 1876 KB Output is correct
11 Correct 62 ms 1884 KB Output is correct
12 Correct 172 ms 1888 KB Output is correct
13 Correct 53 ms 1876 KB Output is correct
14 Correct 107 ms 1884 KB Output is correct
15 Correct 115 ms 1888 KB Output is correct
16 Correct 67 ms 1876 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 17124 KB Output is correct
2 Correct 358 ms 22440 KB Output is correct
3 Correct 357 ms 22276 KB Output is correct
4 Correct 287 ms 17064 KB Output is correct
5 Correct 327 ms 21308 KB Output is correct
6 Correct 295 ms 17628 KB Output is correct
7 Correct 313 ms 19416 KB Output is correct
8 Correct 262 ms 17076 KB Output is correct
9 Correct 281 ms 17028 KB Output is correct
10 Correct 396 ms 22592 KB Output is correct
11 Correct 292 ms 17868 KB Output is correct
12 Correct 355 ms 21976 KB Output is correct
13 Correct 288 ms 17092 KB Output is correct
14 Correct 352 ms 22032 KB Output is correct
15 Correct 370 ms 21984 KB Output is correct
16 Correct 405 ms 17052 KB Output is correct
17 Correct 343 ms 21460 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 17124 KB Output is correct
2 Correct 358 ms 22440 KB Output is correct
3 Correct 357 ms 22276 KB Output is correct
4 Correct 287 ms 17064 KB Output is correct
5 Correct 327 ms 21308 KB Output is correct
6 Correct 295 ms 17628 KB Output is correct
7 Correct 313 ms 19416 KB Output is correct
8 Correct 262 ms 17076 KB Output is correct
9 Correct 281 ms 17028 KB Output is correct
10 Correct 396 ms 22592 KB Output is correct
11 Correct 292 ms 17868 KB Output is correct
12 Correct 355 ms 21976 KB Output is correct
13 Correct 288 ms 17092 KB Output is correct
14 Correct 352 ms 22032 KB Output is correct
15 Correct 370 ms 21984 KB Output is correct
16 Correct 405 ms 17052 KB Output is correct
17 Correct 343 ms 21460 KB Output is correct
18 Incorrect 586 ms 22432 KB Output isn't correct
19 Halted 0 ms 0 KB -