Submission #1225095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225095		emptypringlescan	Sparklers (JOI17_sparklers)	C++17	100 / 100	69 ms	7672 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,k;
	long long t;
	cin >> n >> k >> t;
	long long arr[n];
	for(int i=0; i<n; i++) cin >> arr[i];
	k--;
	long long lo=0,hi=1e9+5,mid;
	while(lo<hi){
		mid=(lo+hi)/2;
		vector<long long> lft,rgt;
		for(int i=0; i<k; i++) lft.push_back(2ll*(arr[i+1]-arr[i]));
		for(int i=n-1; i>k; i--) rgt.push_back(2ll*(arr[i]-arr[i-1]));
		vector<pair<long long,long long> > yr,yl;
		for(int i=0; i<(int)lft.size(); i++){
			pair<long long,long long> x={lft[i]/2ll,max(lft[i]/2ll-t*mid,(long long)-1e10)};
			while(x.second>0&&!yl.empty()&&yl.back().second<=0){
				x.first=max(x.first,x.second+yl.back().first);
				x.second+=yl.back().second;
				yl.pop_back();
			}
			yl.push_back(x);
		}
		for(int i=0; i<(int)rgt.size(); i++){
			pair<long long,long long> x={rgt[i]/2ll,max(rgt[i]/2ll-t*mid,(long long)-1e10)};
			while(x.second>0&&!yr.empty()&&yr.back().second<=0){
				x.first=max(x.first,x.second+yr.back().first);
				x.second+=yr.back().second;
				yr.pop_back();
			}
			yr.push_back(x);
		}
		long long buff=t*mid;
		bool can=true;
		while((!yl.empty()&&yl.back().second<=0)||(!yr.empty()&&yr.back().second<=0)){
			if(!yl.empty()&&yl.back().second<=0&&buff>=yl.back().first){
				buff-=yl.back().second;
				buff=min(buff,(long long)1e10);
				yl.pop_back();
			}
			else if(!yr.empty()&&yr.back().second<=0&&buff>=yr.back().first){
				buff-=yr.back().second;
				buff=min(buff,(long long)1e10);
				yr.pop_back();
			}
			else{
				can=false;
				break;
			}
		}
		for(int i=yl.size()-2; i>=0; i--){
			yl[i].first+=yl[i+1].second;
			yl[i].second+=yl[i+1].second;
		}
		for(int i=yr.size()-2; i>=0; i--){
			yr[i].first+=yr[i+1].second;
			yr[i].second+=yr[i+1].second;
		}
		int degl[n],degr[n],tol[n],tor[n];
		memset(degl,0,sizeof(degl));
		memset(degr,0,sizeof(degr));
		for(int i=0; i<yl.size(); i++){
			long long rm=buff-yl[i].first;
			if(rm<0) can=false;
			int loo=0,hii=yr.size()-1,midd;
			while(loo<hii){
				midd=(loo+hii+1)/2;
				if(yr[midd].second>rm) loo=midd;
				else hii=midd-1;
			}
			if(yr.empty()||yr[loo].second<=rm) tol[i]=-1;
			else{
				tol[i]=loo;
				degr[loo]++;
			}
		}
		for(int i=0; i<yr.size(); i++){
			long long rm=buff-yr[i].first;
			if(rm<0) can=false;
			int loo=0,hii=yl.size()-1,midd;
			while(loo<hii){
				midd=(loo+hii+1)/2;
				if(yl[midd].second>rm) loo=midd;
				else hii=midd-1;
			}
			if(yl.empty()||yl[loo].second<=rm) tor[i]=-1;
			else{
				tor[i]=loo;
				degl[loo]++;
			}
		}
		while(!yl.empty()||!yr.empty()){
			if(!yr.empty()&&degr[(int)yr.size()-1]==0){
				int x=yr.size()-1;
				if(tor[x]!=-1) degl[tor[x]]--;
				yr.pop_back();
			}
			else if(!yl.empty()&&degl[(int)yl.size()-1]==0){
				int x=yl.size()-1;
				if(tol[x]!=-1) degr[tol[x]]--;
				yl.pop_back();
			}
			else{
				can=false;
				break;
			}
		}
		if(can) hi=mid;
		else lo=mid+1;
	}
	cout << (lo+1ll)/2ll;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50