Submission #552920

#TimeUsernameProblemLanguageResultExecution timeMemory
552920hoanghq2004Lightning Conductor (POI11_pio)C++14
27 / 100
110 ms9232 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 5e5 + 10; int n, h[N]; struct Line { int a, b, x; int operator()(int x) { return ceil(sqrt(abs(a - x))) + b; } int operator[](int x) { return ceil(sqrt(abs(a - x))) + b; } int operator < (const Line& other) const { if (x != other.x) return x < other.x; if (a != other.a) return a < other.a; return b < other.b; } }; int intersect(Line L1, Line L2) { int L = max(L1.a, L2.a), R = n + 1; while (R - L > 1) { int mid = L + R >> 1; if (L1[mid] >= L2[mid]) L = mid; else R = mid; } if (L1[L] < L2[L]) return L; else return R; } int bad(Line L1, Line L2, Line L3) { return intersect(L1, L3) <= intersect(L1, L2); } int f[N]; int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> h[i]; vector <Line> convex; for (int i = 1, cur = 0; i <= n; ++i) { if (i > 1) { auto iter = --lower_bound(convex.begin(), convex.end(), (Line){(int)1e9, 0, i}); f[i] = max(f[i], - h[i] + (*iter)(i)); } // if (convex.size() && h[i] <= cur) continue; Line L = {i, h[i], 0}; cur = h[i]; while (convex.size() >= 2 && bad(convex.end()[-2], convex.back(), L)) convex.pop_back(); L.x = (convex.empty() ? 1 : intersect(convex.back(), L)); convex.push_back(L); } convex.clear(); reverse(h + 1, h + n + 1); for (int i = 1, cur = 0; i <= n; ++i) { if (i > 1) { auto iter = --lower_bound(convex.begin(), convex.end(), (Line){(int)1e9, 0, i}); f[n - i + 1] = max(f[n - i + 1], - h[i] + (*iter)(i)); } // if (convex.size() && h[i] <= cur) continue; Line L = {i, h[i], 0}; cur = h[i]; while (convex.size() >= 2 && bad(convex.end()[-2], convex.back(), L)) convex.pop_back(); L.x = (convex.empty() ? 1 : intersect(convex.back(), L)); convex.push_back(L); } for (int i = 1; i <= n; ++i) cout << f[i] << '\n'; }

Compilation message (stderr)

pio.cpp: In function 'int intersect(Line, Line)':
pio.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = L + R >> 1;
      |                   ~~^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...