Submission #787435

#TimeUsernameProblemLanguageResultExecution timeMemory
787435fatemetmhrShortcut (IOI16_shortcut)C++17
0 / 100
2 ms2260 KiB
// ~ Be Name Khoda ~ // #include "shortcut.h" #include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC target("avx2") //#pragma GCC optimize("unroll-loops,Ofast") using namespace std; typedef long long ll; #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define fi first #define se second const int maxn = 1e6 + 10; const int maxn5 = 3e3 + 10; const int maxnt = 1.2e6 + 10; const int maxn3 = 1e3 + 10; const int mod = 1e9 + 7; const int lg = 20; const ll inf = 1e18; int n; ll c; vector <ll> d; ll ps[maxn5], ps2[maxn5]; pair<ll, int> operator +(pair <ll, int> x, ll a){ return mp(x.fi + a, x.se); } pair<ll, int> operator -(pair <ll, int> x, ll a){ return mp(x.fi - a, x.se); } struct RMQ{ int n; pair <ll, int> mx[lg + 1][maxn5]; void build(int N){ n = N; for(int j = 1; j < lg; j++) for(int i = 0; i < n; i++) mx[j][i] = max(mx[j - 1][i], (i + (1 << (j - 1)) < n ? mx[j - 1][i + (1 << (j - 1))] : mp(0ll, 0))); } pair <ll, int> get(int l, int r){ if(l > r) return {0, 0}; int k = 31 - __builtin_clz(r - l + 1); return max(mx[k][l], mx[k][r - (1 << k) + 1]); } } seg1, seg2; ll get_dis(int a, int b){ if(a == b) return 0; if(a > b) swap(a, b); return ps[b] - ps[a]; } pair <ll, int> find_far(int a, int b, int c){ ll disa = get_dis(a, c), disb = get_dis(b, c); //cout << "Wat " << a << ' ' << b << ' ' << c << ' ' << disa << ' ' << disb << endl; disa = min(disa, disb + ::c); disb = min(disb, disa + ::c); int lo = -1, hi = c; while(hi - lo > 1){ int mid = (lo + hi) >> 1; if(get_dis(mid, c) <= min(get_dis(a, mid) + disa, get_dis(b, mid) + disb)) hi = mid; else lo = mid; } int ptl = hi; lo = c; hi = n; while(hi - lo > 1){ int mid = (lo + hi) >> 1; //cout << "check " << mid << ' ' << disa << ' ' << disb << endl; if(get_dis(mid, c) <= min(get_dis(a, mid) + disa, get_dis(b, mid) + disb)) lo = mid; else hi = mid; } int ptr = lo; lo = -1; hi = n; while(hi - lo > 1){ int mid = (lo + hi) >> 1; if(get_dis(mid, a) + disa <= get_dis(mid, b) + disb) lo = mid; else hi = mid; } pair <ll, int> mx = {0, c}; mx = max(mx, seg2.get(ptl, c) - ps2[c]); mx = max(mx, seg1.get(c, ptr) - ps[c]); //cout << mx.fi << ' ' << mx.se << endl; if(lo >= 0) mx = max(mx, seg2.get(0, min(lo, a)) + disa - ps2[a]); if(lo > a) mx = max(mx, seg1.get(a, lo) + disa - ps[a]); //cout << mx.fi << ' ' << mx.se << endl; if(hi < n) mx = max(mx, seg1.get(max(hi, b), n - 1) + disb - ps[b]); //cout << mx.fi << ' ' << mx.se << ' ' << disb << ' ' << ps2[b] << endl; if(hi < b) mx = max(mx, seg2.get(hi, b) + disb - ps2[b]); //cout << "ok " << a << ' ' << b << ' ' << c << ' ' << ptl << ' ' << ptr << ' ' << lo << ' ' << mx.fi << ' ' << mx.se << endl; mx = mx + d[c]; return mx; } ll get_dim(int a, int b){ auto ans1 = find_far(a, b, 0); auto ans2 = find_far(a, b, ans1.se); return ans2.fi; } long long find_shortcut(int N, std::vector<int> l, std::vector<int> D, int C) { n = N; c = C; for(auto u : D) d.pb(u); ps[0] = 0; for(int i = 1; i < n; i++) ps[i] = ps[i - 1] + l[i - 1]; ps2[n - 1] = 0; for(int i = n - 2; i >= 0; i--) ps2[i] = ps2[i + 1] + l[i]; //* for(int i = 0; i < n; i++){ seg1.mx[0][i] = {d[i] + ps[i], i}; seg2.mx[0][i] = {d[i] + ps2[i], i}; } seg1.build(n); seg2.build(n); //*/ ll mn = inf; for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++) mn = min(mn, get_dim(i, j)); return mn; }
#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...