Submission #696191

#	Time	Username	Problem	Language	Result	Execution time	Memory
696191		amirhoseinfar1385	Measures (CEOI22_measures)	C++17	59 / 100	586 ms	22592 KiB

Main

#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 / 10
• Subtask 2: 14 / 14
• Subtask 3: 35 / 35
• Subtask 4: 0 / 41