# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
795417 | 2023-07-27T09:21:06 Z | nonono | Lightning Conductor (POI11_pio) | C++14 | 287 ms | 22880 KB |
#include <bits/stdc++.h> using namespace std; const int mxN = 5e5 + 10; int n; int h[mxN]; long double a[mxN], b[mxN]; deque<array<int, 3>> dq; long double eval(pair<int, int> a, int x) { return (long double)a.second + (long double)sqrt(x - a.first); } int slope(pair<int, int> x, pair<int, int> y) { int low = y.first, right = n; while(low <= right) { int mid = (low + right) / 2; if(sqrt(mid - x.first) + x.second >= sqrt(mid - y.first) + y.second) { low = mid + 1; } else { right = mid - 1; } } return low; } void ins(pair<int, int> newLine) { while(!dq.empty()) { if(newLine.second >= eval({dq.back()[0], dq.back()[1]}, newLine.first)) dq.pop_back(); else { dq.back()[2] = slope({dq.back()[0], dq.back()[1]}, newLine); if(dq.size() > 1 && dq[dq.size() - 2][2] >= dq.back()[2]) dq.pop_back(); else break ; } } dq.push_back({newLine.first, newLine.second, n + 1}); } void solve(long double dp[]) { dq.clear(); for(int i = 1; i <= n; i ++) { ins({i, h[i]}); while(!dq.empty() && dq.front()[2] < i) dq.pop_front(); dp[i] = eval({dq.front()[0], dq.front()[1]}, i); } } int main() { #define taskname "" if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for(int i = 1; i <= n; i ++) cin >> h[i]; solve(a); reverse(h + 1, h + 1 + n); solve(b); reverse(h + 1, h + 1 + n); reverse(b + 1, b + 1 + n); for(int i = 1; i <= n; i ++) cout << (int)ceil(max(a[i], b[i])) - h[i] << "\n"; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 1640 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 2496 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 34 ms | 2832 KB | Output is correct |
2 | Correct | 33 ms | 2808 KB | Output is correct |
3 | Correct | 29 ms | 3128 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 4128 KB | Output is correct |
2 | Correct | 47 ms | 4144 KB | Output is correct |
3 | Correct | 44 ms | 4684 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 109 ms | 9412 KB | Output is correct |
2 | Correct | 117 ms | 9248 KB | Output is correct |
3 | Correct | 105 ms | 9960 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 180 ms | 16116 KB | Output is correct |
2 | Correct | 181 ms | 14036 KB | Output is correct |
3 | Correct | 174 ms | 16144 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 287 ms | 22872 KB | Output is correct |
2 | Correct | 255 ms | 19916 KB | Output is correct |
3 | Correct | 260 ms | 22880 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 265 ms | 20416 KB | Output is correct |
2 | Correct | 270 ms | 19872 KB | Output is correct |
3 | Correct | 241 ms | 22856 KB | Output is correct |