Submission #696345

#	Time	Username	Problem	Language	Result	Execution time	Memory
696345		amirhoseinfar1385	Measures (CEOI22_measures)	C++17	100 / 100	461 ms	34388 KiB

Main

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