Submission #274628

#	Time	Username	Problem	Language	Result	Execution time	Memory
274628		test2	Gap (APIO16_gap)	C++14	0 / 100	35 ms	2168 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 MinMax(ll st , ll en , ll &mn , ll &mx ){

	bool is = 0 ; 
	for(auto u : v){
		if( u >= st && u <= en){
			mx = u ; 
			if(!is){
				mn = u ; 
				is = 1 ; 
			}
		}
	}

	if(!is){
		mn = mx = -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 = 0 , mx = 0 ; 
	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 = 0 , mx = 0 ; 
	ll lo = 0, hi = 1e18 ; 

	while(lo<=hi){
		ll mid  = (lo + hi ) >> 1ll ; 
		MinMax(0 , mid , mx , 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;
}

Compilation message (stderr)

gap.cpp: In function 'll MinMax(ll, ll, ll&, ll&)':
gap.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
   39 | }
      | ^

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