Submission #370944

#	Time	Username	Problem	Language	Result	Execution time	Memory
370944		kshitij_sodani	Snowball (JOI21_ho_t2)	C++14	100 / 100	1746 ms	8804 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'
llo it[200001];
llo mi[200001];
llo ma[200001];
llo n,q;
vector<llo> ss;
bool check(llo mid,llo i){
	if(mid==0){
		return false;
	}
	if(mi[q-1]>0){
		return false;
	}
	if(-mi[q-1]<mid){
		return false;
	}
	//return true;
	llo ind=q-1;
	for(llo j=19;j>=0;j--){
		if(ind-(1<<j)>=0){
			if(mi[ind-(1<<j)]<=0 and (-mi[ind-(1<<j)])>=mid){
				ind-=(1<<j);
			}
		}
	}
	if(i==0){
		return true;
	}
	if((mid)>it[i]-it[i-1]){
		return false;
	}
	//cout<<i<<":"<<mid<<endl;
	//return true;
	if(ind==0){
		return true;
	}
	if(ma[ind-1]+it[i-1]<=it[i]-mid){
		return true;
	}
	return false;

}
bool check2(llo mid,llo i){

	if(mid==0){
		return false;
	}
	if(ma[q-1]<0){
		return false;
	}
	if(ma[q-1]<mid){
		return false;
	}

	//return true;
	llo ind=q-1;
	for(llo j=19;j>=0;j--){
		if(ind-(1<<j)>=0){
			if((ma[ind-(1<<j)])>=mid){
				ind-=(1<<j);
			}
		}
	}
/*	if(i==0){
		cout<<mid<<"::"<<ind<<endl;
	}*/
	/*if(mid==5 and i==0){
		cout<<11<<"::"<<endl;
	}*/
	if(i==n-1){
		return true;
	}
	if((mid)>it[i+1]-it[i]){
		return false;
	}
	//cout<<i<<":"<<mid<<endl;
	//return true;
	if(ind==0){
		return true;
	}

	if(mi[ind-1]+it[i+1]>=it[i]+mid){
		return true;
	}
	return false;

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin>>n>>q;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	/*llo q;
	cin>>q;*/
	llo su=0;
	for(llo i=0;i<q;i++){
		llo aa;
		cin>>aa;
		su+=aa;
		ss.pb(su);
	}
	mi[0]=ss[0];
	ma[0]=ss[0];
	for(llo i=1;i<ss.size();i++){
		mi[i]=min(mi[i-1],ss[i]);
		ma[i]=max(ma[i-1],ss[i]);
	}
/*	for(llo i=0;i<q;i++){
		cout<<mi[i]<<":";
	}
	cout<<endl;*/
	for(llo i=0;i<n;i++){
		llo low=0;
		llo high=1e18;
		while(low<high-1){
			llo mid=(low+high)/2;
			if(check(mid,i)){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		llo ind=low;
		if(check(high,i)){
			ind=max(ind,high);
		}
		//cout<<ind<<":"<<endl;
		low=0;
		high=1e18;
		while(low<high-1){
			llo mid=(low+high)/2;
			if(check2(mid,i)){
				low=mid;
			}
			else{
				high=mid;
			}
		}
		llo ind2=low;
		if(check2(high,i)){
			ind2=max(ind2,high);
		}
		cout<<ind+ind2<<endl;
	}







 
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:115:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(llo i=1;i<ss.size();i++){
      |              ~^~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67