| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 274631 | test2 | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
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;
}