oj.uz

Submission #696197

# Submission time Handle Problem Language Result Execution time Memory
696197 2023-02-05T19:40:30 Z amirhoseinfar1385 Measures (CEOI22_measures) C++17
24 / 100
 237 ms 30708 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)].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]);
	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 16724 KB Output is correct
2 Correct 8 ms 16748 KB Output is correct
3 Correct 11 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16724 KB Output is correct
6 Correct 9 ms 16852 KB Output is correct
7 Correct 9 ms 16748 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 16724 KB Output is correct
2 Correct 8 ms 16748 KB Output is correct
3 Correct 11 ms 16724 KB Output is correct
4 Correct 10 ms 16724 KB Output is correct
5 Correct 8 ms 16724 KB Output is correct
6 Correct 9 ms 16852 KB Output is correct
7 Correct 9 ms 16748 KB Output is correct
8 Correct 8 ms 16752 KB Output is correct
9 Correct 125 ms 18380 KB Output is correct
10 Correct 179 ms 18496 KB Output is correct
11 Correct 75 ms 18388 KB Output is correct
12 Correct 196 ms 18420 KB Output is correct
13 Correct 68 ms 18308 KB Output is correct
14 Correct 126 ms 18620 KB Output is correct
15 Correct 122 ms 18332 KB Output is correct
16 Correct 78 ms 18328 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 41.0

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