Submission #274780

#	Time	Username	Problem	Language	Result	Execution time	Memory
274780		test2	Gap (APIO16_gap)	C++14	3.91 / 100	1554 ms	1300 KiB

gap

#include <bits/stdc++.h>
#include <stdlib.h>

#include "gap.h"

#define I inline void 

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

using namespace std ; 

const int mod = 1e9 + 7 ; 

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 , mx ; 
	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 ; 
	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