Submission #274692

#	Time	Username	Problem	Language	Result	Execution time	Memory
274692		test2	Gap (APIO16_gap)	C++14	3.91 / 100	1620 ms	1272 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")

#define I inline void 

using ll = long long ; 
using ld = long double ; 

using namespace std ; 

const int mod = 1e9 + 7 ; 

// how interesting!

int n; 

vector<ll> v ; 
ll zero = -1 ; 
struct node{
	ll pref = 0 , suff = 0 , summ = 0 , mxx = 0 ; 

	I maint(){
		mxx = max(max(mxx , pref) , max(suff , summ)) ; 
	}

	node(){

	}

	node(ll x){
		pref = suff = summ = x ; 
		maint() ; 
	}

	I merge(node &rhs){
		ll npref = 0 , nsuff = 0 , nsumm = 0 ; 
		if(summ){
			npref = summ + rhs.pref ; 
		}
		else npref = pref ;

		if(summ && rhs.summ){
			nsumm = summ + rhs.summ ; 
		}

		if(rhs.summ){
			nsuff = rhs.summ + suff ;
		}
		else nsuff = rhs.suff ; 
		mxx = max(mxx , suff + rhs.pref) ; 

		pref = npref ; 
		summ = nsumm ; 
		suff = nsuff ;
		mxx = max(mxx , rhs.mxx) ; 
		maint() ; 
	}
} ; 

node query(ll L , ll R){

	ll *mn = &zero  , *mx = &zero; 
	if(L == R){
		MinMax(L , R , mn , mx) ; 
		return node( (*mn) == -1) ; 
	}

	ll mid = (L + R) >> 1ll ; 
	MinMax(L , R , mn , mx) ; 

	if( (*mn) == -1){
		return node(R - L + 1) ; 
	}
	if(L == R)
		return node(0) ; 
	node lhs = query(L , mid) ; 
	node rhs = query(mid+1 , R) ;
	lhs.merge(rhs) ; 
	return lhs ;  
}

long long findGap(int T, int N)
{

	ll st = 0 , en = 1e18 ; 
	
	ll *mn , *mx ; 
	mn =  mx = &zero ; 
	ll lo = 0, hi = 1e18 ; 
 
	while(lo<=hi){
		ll mid  = (lo + hi ) >> 1ll ; 
		MinMax(0 , mid , mn , mx) ; 
		if( (*mx) != -1){
			st = mid ; 
			hi = mid -1 ; 
		}
		else lo = mid + 1; 
	}

	lo = 0 , hi = 1e18 ; 
	while(lo<=hi){
		ll mid = (lo + hi ) >> 1ll ; 
		MinMax(mid , 1e18 , mn , mx ) ; 
		if( (*mx) != -1){
			en = mid ; 
			lo = mid +1 ; 
		}
		else 
			hi = mid - 1; 
	}

	node answer = query(st , en) ; 
	return answer.mxx + 1; 

	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 3.9074132609 / 70