oj.uz

Submission #696186

# Submission time Handle Problem Language Result Execution time Memory
696186 2023-02-05T18:26:56 Z amirhoseinfar1385 Measures (CEOI22_measures) C++17
24 / 100
 286 ms 17744 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){
			return ;
		}
		if(l>=tl&&r<=tr){
			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;
	}
	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 long tagh=fz/2;
					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);
			if(dp>ft){
				if(dp-ft>fres){
					long double fz=dp-ft-fres;
					long long tagh=fz/2;
					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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 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 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 115 ms 1876 KB Output is correct
10 Correct 168 ms 1876 KB Output is correct
11 Correct 63 ms 1896 KB Output is correct
12 Correct 172 ms 1876 KB Output is correct
13 Correct 54 ms 1876 KB Output is correct
14 Correct 108 ms 1900 KB Output is correct
15 Correct 107 ms 1888 KB Output is correct
16 Correct 68 ms 1892 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 17744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 17744 KB Output isn't correct
2 Halted 0 ms 0 KB -