Submission #603092

#TimeUsernameProblemLanguageResultExecution timeMemory
6030928e7Shortcut (IOI16_shortcut)C++17
97 / 100
2033 ms110288 KiB
#include "shortcut.h" //Challenge: Accepted #include <bits/stdc++.h> #pragma GCC optimize("Ofast") using namespace std; #ifdef zisk void debug(){cout << endl;} template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);} template<class T> void pary(T l, T r){ while (l != r) cout << *l << " ", l++; cout << endl; } #else #define debug(...) 0 #define pary(...) 0 #endif #define ll long long #define maxn 1000005 #define pii pair<ll, ll> #define ff first #define ss second const ll inf = 1LL<<58; long long find_shortcut(int n, vector<int> L, vector<int> D, int C) { vector<ll> p(n), lef(n+1, -inf), rig(n+1, -inf), tmp(n), vl(n+1, -inf), vr(n+1, -inf); vector<pii> ls(n), rs(n), a(n); for (int i = 1;i < n;i++) p[i] = p[i-1] + L[i-1]; for (int i = 0;i < n;i++) { a[i] = {p[i] + D[i], i}; vl[i] = D[i] - p[i]; vr[i] = D[i] + p[i]; } sort(a.begin(), a.end()); for (int i = 0;i < n;i++) { int id = a[i].ss; lef[i] = D[id] - p[id]; rig[i] = D[id] + p[id]; ls[i] = {id, n}; rs[i] = {id, n}; } for (int i = n - 2;i >= 0;i--) { int se = ls[i].ff; if (vl[ls[i+1].ff] < vl[se]) { se = ls[i+1].ff; } else { ls[i].ff = ls[i+1].ff; } if (vl[se] > vl[ls[i+1].ss]) ls[i].ss = se; else ls[i].ss = ls[i+1].ss; se = rs[i].ff; if (vr[rs[i+1].ff] < vr[se]) { se = rs[i+1].ff; } else { rs[i].ff = rs[i+1].ff; } if (vr[se] > vr[rs[i+1].ss]) rs[i].ss = se; else rs[i].ss = rs[i+1].ss; } rig.pop_back(), lef.pop_back(); pary(lef.begin(), lef.end()); pary(rig.begin(), rig.end()); for (int i = 0;i < n;i++) debug("lef", i, ls[i].ff, ls[i].ss); ll low = 0, up = inf; while (low < up - 1) { ll M = (low + up) / 2; ll lb = -inf, rb = inf, db = -inf, ub = inf; debug("M", M); for (int i = 0;i < n-1;i++) { int ind = upper_bound(rig.begin(), rig.end(), M - (D[i] - p[i])) - rig.begin(); //[ind, n); debug(i, ind, ls[ind].ff, ls[ind].ss); if (ind == n) continue; ll len = M - D[i] - C; ll l = (rs[ind].ff != i ? vr[rs[ind].ff] : vr[rs[ind].ss]) - len, r = -(ls[ind].ff != i ? vl[ls[ind].ff] : vl[ls[ind].ss]) + len; debug("l", l, "r", r); //square with two points at [l, r] lb = max(lb, p[i] - r); rb = min(rb, p[i] - l); db = max(db, p[i] + l); ub = min(ub, p[i] + r); } debug(M, lb, rb, db, ub); if (rb < lb || ub < db) low = M; else { bool good = 0; for (int i = 0;i < n;i++) { ll mi = max(db - p[i], -rb + p[i]); ll ma = min(ub - p[i], -lb + p[i]); int ind = lower_bound(p.begin(), p.end(), mi) - p.begin(); if (ind != n && p[ind] <= ma) { good = 1; break; } } if (good) up = M; else low = M; } } return up; } /* 2 4 10 28 37 2 1 3 7 2 */

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
shortcut.cpp:61:2: note: in expansion of macro 'pary'
   61 |  pary(lef.begin(), lef.end());
      |  ^~~~
shortcut.cpp:15:19: warning: statement has no effect [-Wunused-value]
   15 | #define pary(...) 0
      |                   ^
shortcut.cpp:62:2: note: in expansion of macro 'pary'
   62 |  pary(rig.begin(), rig.end());
      |  ^~~~
shortcut.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
shortcut.cpp:63:28: note: in expansion of macro 'debug'
   63 |  for (int i = 0;i < n;i++) debug("lef", i, ls[i].ff, ls[i].ss);
      |                            ^~~~~
shortcut.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
shortcut.cpp:70:3: note: in expansion of macro 'debug'
   70 |   debug("M", M);
      |   ^~~~~
shortcut.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
shortcut.cpp:74:4: note: in expansion of macro 'debug'
   74 |    debug(i, ind, ls[ind].ff, ls[ind].ss);
      |    ^~~~~
shortcut.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
shortcut.cpp:79:4: note: in expansion of macro 'debug'
   79 |    debug("l", l, "r", r);
      |    ^~~~~
shortcut.cpp:14:20: warning: statement has no effect [-Wunused-value]
   14 | #define debug(...) 0
      |                    ^
shortcut.cpp:86:3: note: in expansion of macro 'debug'
   86 |   debug(M, lb, rb, db, ub);
      |   ^~~~~
#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...