Submission #1073331

#TimeUsernameProblemLanguageResultExecution timeMemory
1073331WansurShortcut (IOI16_shortcut)C++14
97 / 100
1014 ms59216 KiB
#include <bits/stdc++.h> #include "shortcut.h" #define f first #define s second #define ent '\n' typedef long long ll; using namespace std; const int maxn = 1e6 + 12; int L[maxn], prmn[maxn]; int R[maxn], sfmx[maxn]; bool add[maxn]; int posq[maxn]; int p[maxn], q[maxn], l[maxn]; ll mx[maxn], mn[maxn]; ll pref[maxn], d[maxn]; int n, c; void upd(int i, ll x){ for(; i <= n; i |= (i + 1)){ mx[i] = max(mx[i], x); } } ll get(int i){ ll Mx = -1e18; for(; i > 0; i = (i & (i + 1)) - 1){ Mx = max(Mx, mx[i]); } return Mx; } bool check2(ll D){ ll x1 = 0, x2 = 1e18, y1 = 0, y2 = 1e18; for(int i=0;i<=n;i++){ mx[i] = -1e18; } for(int i=1, j=0;i<=n;i++){ while(j < n && pref[p[j+1]] - d[p[j+1]] < pref[q[i]] + d[q[i]] - D){ j++; upd(p[j], pref[p[j]] + d[p[j]]); add[p[j]] = 1; } ll mx = get(q[i]-1); ll x = p[L[q[i]]], mn = pref[x] - d[x]; if(mn >= 1e17 || mn >= pref[q[i]] + d[q[i]] - D) continue; ll ly = mx + d[q[i]] + c - D, ry = mn + D - d[q[i]] - c; x2 = min(x2, pref[q[i]] + ry); y1 = max(y1, pref[q[i]] - ry), y2 = min(y2, pref[q[i]] - ly); } for(int i=n;i;i--){ ll x = q[R[p[i]]], mx = pref[x] + d[x]; if(mx > pref[p[i]] - d[p[i]] + D && x > p[i]){ x1 = max(x1, mx + pref[p[i]] + d[p[i]] + c - D); } } if(x1 > x2 || y1 > y2) return 0; for(int i=n, j = 1;i;i--){ while(j <= n && x1 - pref[i] > pref[j]){ j++; } l[i] = j; } for(int i=1, j=1;i<=n;i++){ while(j <= n && pref[i] - y2 > pref[j]){ j++; } l[i] = max(l[i], j); if(l[i] < i && y1 <= pref[i] - pref[l[i]] && pref[i] - pref[l[i]] <= y2 && x1 <= pref[i] + pref[l[i]] && pref[i] + pref[l[i]] <= x2){ return 1; } } return 0; } bool check(ll D){ if(n <= 3e5){ return check2(D); } ll x1 = 0, x2 = 1e18, y1 = 0, y2 = 1e18; for(int i=1;i<=n;i++){ ll x = q[R[i]], mx = pref[x] + d[x]; x = p[L[i]]; ll mn = pref[x] - d[x]; if(mn >= 1e17 || mn >= pref[i] + d[i] - D) continue; ll ry = mn + D - d[i] - c; x2 = min(x2, pref[i] + ry); y1 = max(y1, pref[i] - ry); } for(int t=1, j = 0;t<=n;t++){ int i = q[t]; int x = 0, y = 0; while(pref[p[j+1]] - d[p[j+1]] < pref[i] + d[i] - D){ j++; if(pref[p[j]] + d[p[j]] > pref[x] + d[x] || x == 0){ y = x; x = p[j]; } else if(pref[p[j]] + d[p[j]] > pref[y] + d[y] || y == 0){ y = p[j]; } } if(x != i){ if(x != 0) { y2 = min(y2, pref[i] - pref[x] - d[x] - d[i] - c + D); x1 = max(x1, pref[i] + pref[x] + d[x] + d[i] + c - D); } } else{ if(y != 0) { y2 = min(y2, pref[i] - pref[y] - d[y] - d[i] - c + D); x1 = max(x1, pref[i] + pref[y] + d[y] + d[i] + c - D); } } } if(x1 > x2 || y1 > y2) return 0; for(int i=n, j = 1;i;i--){ while(j <= n && x1 - pref[i] > pref[j]){ j++; } l[i] = j; } for(int i=1, j=1;i<=n;i++){ while(j <= n && pref[i] - y2 > pref[j]){ j++; } l[i] = max(l[i], j); if(l[i] < i && y1 <= pref[i] - pref[l[i]] && pref[i] - pref[l[i]] <= y2 && x1 <= pref[i] + pref[l[i]] && pref[i] + pref[l[i]] <= x2){ return 1; } } return 0; } ll find_shortcut(int N, vector<int> l, vector<int> D, int C){ n = N, c = C; for(int i=2;i<=n;i++){ pref[i] = pref[i-1] + l[i-2]; } for(int i=1;i<=n;i++){ d[i] = D[i-1]; p[i] = i; q[i] = i; } sort(p+1, p+n+1, [](int i, int j){ return pref[i] - d[i] < pref[j] - d[j]; }); sort(q+1, q+n+1, [](int i, int j){ return pref[i] + d[i] < pref[j] + d[j]; }); prmn[0] = 1e9; for(int i=1;i<=n;i++){ prmn[i] = min(prmn[i-1], p[i]); } sfmx[n+1] = -1e9; for(int i=n;i;i--){ sfmx[i] = max(sfmx[i+1], q[i]); } p[n+1] = n + 1; pref[n+1] = 1e18; pref[0] = -1e18; for(int i=1;i<=n;i++){ L[i] = n + 1, R[i] = 0; for(int l=1, r=n;l<=r;){ int mid = l + r >> 1; if(prmn[mid] < i){ L[i] = mid; r = mid - 1; } else l = mid + 1; } for(int l=1, r=n;l<=r;){ int mid = l + r >> 1; if(sfmx[mid] > i){ R[i] = mid; l = mid + 1; } else r = mid - 1; } } ll ans = 0; for(ll l = 0, r = 1e15 + 2e9; l <= r;){ ll mid = l + r >> 1; bool c = 0; if(check(mid)){ ans = mid; r = mid - 1; } else{ l = mid + 1; } } return ans; }

Compilation message (stderr)

shortcut.cpp: In function 'bool check(ll)':
shortcut.cpp:83:25: warning: unused variable 'mx' [-Wunused-variable]
   83 |         ll x = q[R[i]], mx = pref[x] + d[x];
      |                         ^~
shortcut.cpp: In function 'll find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:166:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |             int mid = l + r >> 1;
      |                       ~~^~~
shortcut.cpp:174:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  174 |             int mid = l + r >> 1;
      |                       ~~^~~
shortcut.cpp:184:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  184 |         ll mid = l + r >> 1;
      |                  ~~^~~
shortcut.cpp:185:14: warning: unused variable 'c' [-Wunused-variable]
  185 |         bool c = 0;
      |              ^
#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...