Submission #502886

#TimeUsernameProblemLanguageResultExecution timeMemory
502886dooweyShortcut (IOI16_shortcut)C++14
71 / 100
2085 ms2120 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, int> pii; #define fi first #define se second #define mp make_pair const int N = (int)1e6 + 10; int n; ll X[N]; vector<ll> W; ll L; vector<pii> A,B; bool check(ll k){ ll mx = 0; for(int i = 0 ; i < n; i ++ ){ if(W[i] + mx > k) return false; mx = max(mx, W[i]); } ll lowplus = -(ll)1e18; ll highplus = (ll)1e18; ll lowminus = -(ll)1e18; ll highminus = (ll)1e18; for(int i = 0 ; i < n; i ++ ){ for(int j = 0; j < n; j ++ ){ if(i == j) continue; if(X[j] + W[j] - X[i] + W[i] <= k) continue; // no one cares lowplus = max(lowplus, -k + X[i] + X[j] + L + W[i] + W[j]); highplus = min(highplus, k + X[i] + X[j] - L - W[i] - W[j]); lowminus = max(lowminus, -k + X[i] - X[j] + L + W[i] + W[j]); highminus = min(highminus, k + X[i] - X[j] - L - W[i] - W[j]); } } int i0 = n - 1, j0 = n - 1; int i1 = 0, j1 = 0; int tl, tr; for(int i = 0 ; i < n; i ++ ){ while(i0 >= 0 && X[i] + X[i0] > highplus){ i0 -- ; } while(j0 > 0 && X[i] + X[j0 - 1] >= lowplus){ j0 -- ; } while(i1 < n && X[i] - X[i1] > highminus){ i1 ++ ; } while(j1 + 1 < n && X[i] - X[j1 + 1] >= lowminus){ j1 ++ ; } tl = i + 1; tr = n - 1; tl = max(tl, j0); tr = min(tr, i0); tl = max(tl, i1); tr = min(tr, j1); if(tl <= tr){ return true; } } return false; } ll find_shortcut(int _n, vector<int> l, vector<int> _d, int _c){ n = _n; for(int i = 1; i < n; i ++ ){ X[i] = X[i - 1] + l[i - 1]; } for(auto x : _d) W.push_back(x); L = _c; ll li = 0; ll ri = (ll)1e16; ll mid; while(li < ri){ mid = (li + ri) / 2; if(check(mid)){ ri = mid; } else{ li = mid + 1; } } return li; }
#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...