Submission #906955

#TimeUsernameProblemLanguageResultExecution timeMemory
906955ByeWorldGap (APIO16_gap)C++14
0 / 100
3078 ms524288 KiB
#include "gap.h" #include <bits/stdc++.h> #define bupol __builtin_popcount //#define int long long #define ll long long #define ld long double #define fi first #define se second #define pb push_back #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) using namespace std; const int MAXN = 1e5+5; const int MAXK = 205; const int LOG = 20; const int MOD = 1e9+7; const int SQRT = 520; const ll INF = 1e18+10; typedef pair<ll,ll> pii; typedef pair<ll,pii> ipii; ll mn, mx; ll x, y; int n; set<ll> s; ll ans = -INF; vector <pii> vec; void split(ll x, ll y){ if(x >= y) return; vec.clear(); vec.pb(pii(x, (x+x+y)/3)); vec.pb(pii((x+x+y)/3+1, (x+y+y)/3) ); vec.pb(pii((x+y+y)/3+1, y)); } // sol(tmn, ((tmn+tmx)>>1) ); // //cout << ((tmn+tmx)>>1)+1 << ' '<< tmx << " oo\n"; // sol(((tmn+tmx)>>1)+1, tmx); void sol(ll l, ll r){ // cari semua di range l-r cout << l << ' '<< r << " p\n"; if(l > r) return; MinMax(l, r, &mn, &mx); if(mn == -1) return; // gk ada s.insert(mn); s.insert(mx); if(r-l+1 <= 2) return; int tmn = mn, tmx = mx; tmn++; tmx--; split(tmn, tmx); for(auto in : vec) sol(in.fi, in.se); } long long findGap(int T, int N) { n = N; sol(0, INF); //for(auto in : s) cout << in << " xx\n"; auto it = s.begin(); ll las = -1; while(it != s.end()){ if(las != -1) ans = max(ans, (*it)-las); las = (*it); it++; } //for(auto in : s) cout << in << " in\n"; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...