Submission #1051667

#TimeUsernameProblemLanguageResultExecution timeMemory
1051667Alihan_8Shortcut (IOI16_shortcut)C++17
71 / 100
2063 ms54364 KiB
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define ar array #define all(x) x.begin(), x.end() using i64 = long long; const i64 inf = 1e15; struct square{ i64 x1, x2, y1, y2; square(i64 x1 = 0, i64 x2 = 0, i64 y1 = 0, i64 y2 = 0) : x1(x1), x2(x2), y1(y1), y2(y2) {} square f(square q){ return square(max(x1, q.x1), min(x2, q.x2), max(y1, q.y1), min(y2, q.y2)); } bool check(i64 x, i64 y){ return x1 <= x && x2 >= x && y1 <= y && y2 >= y; } }; struct SegTree{ vector <ar<i64,2>> T; int n; bool isMax; SegTree(int n, bool isMax = false) : n(n), isMax(isMax) { T.resize(n * 4 + 5, {inf, -1}); } void upd(int v, int l, int r, int p, i64 x, int j){ if ( l == r ){ if ( T[v][0] > x ){ T[v] = {x, j}; } return; } int m = (l + r) / 2; if ( p <= m ) upd(v * 2, l, m, p, x, j); else upd(v * 2 + 1, m + 1, r, p, x, j); T[v] = min(T[v * 2], T[v * 2 + 1]); } void upd(int p, i64 x, int j){ if ( isMax ) x = -x; upd(1, 0, n, p, x, j); } ar <i64,2> get(int v, int l, int r, int tl, int tr){ ar <i64,2> ret = {inf, -1}; if ( l > tr or r < tl ) return ret; if ( tl <= l && tr >= r ){ return T[v]; } int m = (l + r) / 2; return min(get(v * 2, l, m, tl, tr), get(v * 2 + 1, m + 1, r, tl, tr)); } int get(int l, int r){ return get(1, 0, n, l, r)[1]; } }; long long find_shortcut(int n, std::vector<int> L, std::vector<int> d, int C){ vector <i64> x(n), A(n), B(n); for ( int i = 1; i < n; i++ ){ x[i] = x[i - 1] + L[i - 1]; } for ( int i = 0; i < n; i++ ){ A[i] = x[i] + d[i]; B[i] = x[i] - d[i]; } auto P = B; P.pb(-inf), P.pb(inf); sort(all(P)); P.resize(unique(all(P)) - P.begin()); int m = P.size(); auto get = [&](i64 x){ return lower_bound(all(P), x) - P.begin(); }; auto ok = [&](i64 k){ i64 kk = k - C; vector <ar<i64,3>> pt; auto add = [&](int i, int j){ if ( i == -1 ) return; pt.pb({x[i] + x[j], x[i] - x[j], kk - (d[i] + d[j])}); }; vector <SegTree> seg(4, SegTree(m)); seg[1] = seg[3] = SegTree(m, 1); for ( int i = 0; i < n; i++ ){ int u = get(A[i] - k) - 1, v = get(B[i]); vector <i64> q = {A[i], A[i], B[i], B[i]}; for ( int j = 0; j < 4; j++ ){ add(seg[j].get(0, u), i); seg[j].upd(v, q[j], i); } } if ( pt.empty() ) return true; auto [X, Y, d] = pt[0]; square t = square(X - d, X + d, Y - d, Y + d); for ( int i = 1; i < (int)pt.size(); i++ ){ auto [x, y, d] = pt[i]; t = t.f(square(x - d, x + d, y - d, y + d)); } if ( t.x1 > t.x2 || t.y1 > t.y2 ){ // area 0 return false; } bool flag = false; int l = n, r = n - 1; set <i64> st; for ( int i = 0; i < n; i++ ){ while ( l > 0 && t.x1 - x[i] <= x[l - 1] ){ st.insert(x[--l]); } while ( r >= 0 && t.x2 - x[i] < x[r] ){ st.erase(x[r--]); } i64 p = -t.y2 + x[i], q = -t.y1 + x[i]; if ( l <= i && r >= i ) st.erase(x[i]); if ( st.lower_bound(p) != st.upper_bound(q) ){ flag = true; } if ( l <= i && r >= i ) st.insert(x[i]); } //~ for ( int i = 0; i < n; i++ ){ //~ for ( int j = i + 1; j < n; j++ ){ //~ flag |= t.check(x[i] + x[j], x[i] - x[j]); //~ } //~ } return flag; }; i64 l = 0, r = 1e15; while ( l < r ){ i64 m = (l + r) / 2; if ( ok(m) ){ r = m; } else l = m + 1; } return l; }
#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...