Submission #425954

#TimeUsernameProblemLanguageResultExecution timeMemory
425954jtnydv25Shortcut (IOI16_shortcut)C++17
97 / 100
2068 ms47736 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define all(c) ((c).begin()), ((c).end()) #define sz(x) ((int)(x).size()) #ifdef LOCAL #include <print.h> #else #define trace(...) #define endl '\n' #endif const int N = 1 << 20; const ll INF = 1e18; ll A[N], B[N]; ll p[N]; int perm1[N], perm2[N]; long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c){ for(int i = 1; i < n; i++) p[i] = p[i - 1] + l[i - 1]; iota(perm1, perm1 + n, 0); iota(perm2, perm2 + n, 0); sort(perm1, perm1 + n, [&](int i, int j){return d[i] - p[i] > d[j] - p[j];}); sort(perm2, perm2 + n, [&](int i, int j){return d[i] + p[i] < d[j] + p[j];}); int mx = 0, mx2 = 0, ind_mx = 0; A[0] = -INF; B[0] = INF; for(int i = 1; i <= n; i++){ int ind = perm1[i - 1]; A[i] = max(A[i - 1], p[ind] + d[ind]); B[i] = min(B[i - 1], p[ind] - d[ind]); if(d[ind] > mx){ mx2 = mx; mx = d[ind]; ind_mx = ind; } else if(d[ind] > mx2) mx2 = d[ind]; } ll lo = mx + mx2, hi = p[n - 1] / 2 + 3e9; lo = max(lo, (p[n - 1] - 1000000000) / 3); while(lo < hi){ ll D = (lo + hi) / 2; ll L1 = -INF, R1 = INF; ll L2 = -INF, R2 = INF; int cur = 0; for(int ind = 0; ind < n; ind++){ int i = perm2[ind]; while(cur < n && d[perm1[cur]] + d[i] + p[i] - p[perm1[cur]] > D) cur++; ll a = A[cur], b = B[cur]; if(D < 2 * mx && i == ind_mx){ a = -INF; b = INF; for(int r = 0; r < cur; r++){ int _r = perm1[r]; if(_r == i) continue; a = max(a, p[_r] + d[_r]); b = min(b, p[_r] - d[_r]); } } L1 = max(L1, a + d[i] + c - p[i] - D); R1 = min(R1, b - d[i] - c - p[i] + D); L2 = max(L2, a + p[i] - D + d[i] + c); R2 = min(R2, b + p[i] + D - d[i] - c); } if(L1 > R1 || L2 > R2){ lo = D + 1; continue; } bool ok = false; int ptr1 = 0; int ptr2 = n; for(int v = 1; v < n; v++){ while(ptr1 < n && p[ptr1] - p[v] < L1) ptr1++; while(ptr2 > 0 && p[ptr2 - 1] + p[v] >= L2) ptr2--; int u = max(ptr1, ptr2); if(u >= v) continue; if(p[u] - p[v] > R1 || p[u] + p[v] > R2) continue; ok = true; break; } if(ok) hi = D; else lo = D + 1; } return lo; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...