Submission #1193189

#TimeUsernameProblemLanguageResultExecution timeMemory
1193189emad234Gap (APIO16_gap)C++20
83.51 / 100
43 ms2352 KiB
#include "gap.h" #include <bits/stdc++.h> #define ll long long #define F first #define S second #define pii pair<int, int> const int mxN = 4e5 + 5; using namespace std; long long findGap(int T, int N) { ll l,r; MinMax(0,1e18,&l,&r); if(r - l + 1 == N) return 1; if(T == 1){ vector<ll>v; v.push_back(l); v.push_back(r); l++; r--; N -= 2; while(N > 0){ MinMax(l,r,&l,&r); if(l == -1 || r == -1) break; v.push_back(l); v.push_back(r); l++; r--; N -= 2; } sort(v.begin(),v.end()); ll bg = v[0]; ll ans = 0; for(auto x : v){ ans = max(ans,x - bg); bg = x; } return ans; } ll buck = (r - l + 1) / N; buck += (((r - l + 1) % N) != 0); ll prvT = -1; ll ans = buck; buck++; for(ll i = l; i <= r;i += buck){ ll s = i,t = min(r, i + buck - 1); ll mx,mn; MinMax(s,t,&mn,&mx); // cout<<s<<' '<<t<<' '<<mx<<' '<<mn<<'\n'; if(prvT != -1 && mn != -1) ans = max(ans, mn - prvT); if(mx != -1) prvT = mx; } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...