# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
68199 | gusfring | Gap (APIO16_gap) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "gap.h"
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const ll MAXA = 1000000000000000000LL;
ll mn, mx;
ll solve(ll lo, ll hi){
if(lo >= hi) return 0;
unsigned long long x = (1LLU * lo + hi) / 2;
ll mid = (ll)(x), mn1 = -1, mx1 = -1, mn2 = -1, mx2 = -1;
if(lo < mid) MinMax(lo, mid, &mn1, &mx1);
if(mid + 1 < hi) MinMax(mid + 1, hi, &mn2, &mx2);
ll res = 0, r1 = 0, r2 = 0;
if(mx1 != -1 && mx2 != -1) res = mn2 - mx1;
if(mx2 != -1 && mx2 != mn2) r2 = solve(mn2, mx2);
if(mx1 != -1 && mx1 != mn1) r1 = solve(mn1, mx1);
return max({res, r1, r2});
}
long long findGap(int T, int N){
MinMax(0, MAXA, &mn, &mx);
return solve(mn, mx);
}