제출 #101836

#제출 시각아이디문제언어결과실행 시간메모리
101836cerberusGap (APIO16_gap)C++17
100 / 100
65 ms1448 KiB
/* cerberus97 - Hanit Banga */ #include <iostream> #include <iomanip> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <map> #include <set> #include <queue> #include <stack> #include <vector> #include <algorithm> #ifndef LOCAL #include "gap.h" #endif using namespace std; #define pb push_back #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL) typedef long long ll; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const ll INF = 1e18; ll findGap(int T, int N); ll findGap_small(int N); void query(ll s, ll t, ll &mn, ll &mx, int T); int M; set<pll> S; #ifdef LOCAL int main() { int T, n; cin >> T >> n; vector<ll> v(n); for (int i = 1; i <= n; ++i) { cin >> v[i - 1]; } sort(v.begin(), v.end()); for (int i = 0; i < n; ++i) { S.insert({v[i], i}); } S.insert({-1, -1}); S.insert({INF + 1, n}); cout << findGap(T, n) << endl << M << ' '; if (T == 1) { cout << (n + 1) / 2 << endl; } else { cout << 3 * n << endl; } } #endif ll findGap(int T, int N) { if (T == 1) { return findGap_small(N); } ll mn, mx; query(0, INF, mn, mx, T); if (N <= 2) { return mx - mn; } ll A = mn, B = mx, best = (B - A + N - 2) / (N - 1), sz = best + 1; while (A < B) { if (A + sz >= B) { query(A + 1, B - 1, mn, mx, T); mx = B; if (mn == -1) { mn = B; } } else { query(A + 1, A + sz, mn, mx, T); } if (mn == -1) { sz *= 2; continue; } best = max(best, mn - A); sz = best + 1; A = mx; } return best; } ll findGap_small(int N) { ll mn, mx; query(0, INF, mn, mx, 1); ll best = 0; ll A = mn, B = mx; N -= 2; while (A < B and N > 0) { query(A + 1, B - 1, mn, mx, 1); if (mn == -1) { best = max(best, B - A); break; } else { best = max(best, mn - A); best = max(best, B - mx); A = mn; B = mx; N -= 2; } } return max(best, B - A); } void query(ll s, ll t, ll &mn, ll &mx, int T) { if (s > t) { mn = mx = -1; return; } #ifdef LOCAL assert(s <= t); ++M; auto l = S.lower_bound({s, -INF}); auto r = S.upper_bound({t, INF + 10}); --r; if (l->second <= r->second) { mn = l->first; mx = r->first; if (T == 2) { M += (r->second - l->second + 1); } } else { mn = mx = -1; } #else MinMax(s, t, &mn, &mx); #endif }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...