## Submission #167479

# Submission time Handle Problem Language Result Execution time Memory
167479 2019-12-08T16:28:33 Z Thuleanx Lightning Conductor (POI11_pio) C++14
100 / 100
166 ms 27988 KB
```#include <bits/stdc++.h>
using namespace std;

const int N = 5e5+7;
int n;
int h[N];
int L[N], R[N];
double sqr[N];

struct Sol {
int i, high;
Sol(int i, int high):i(i), high(high) {}
int value(int j) { return high + ceil(sqr[j-i]); }
double actual_value(int j) { return high + sqr[j-i]; }
int to(Sol &other) {
int lo = other.i, hi = n-1;
while (lo <= hi) {
int mid = lo+hi>>1;
if (actual_value(mid) >= other.actual_value(mid)) 	lo = mid+1;
else												hi = mid-1;
}
return lo;
}
};

void solve(int A[]) {
deque<Sol> dq;
int hi = -1;
for (int i = 0; i < n; i++) {
while (dq.size() >= 2 && dq[0].to(dq[1]) <= i)
dq.pop_front();
if (dq.size())
A[i] = dq.front().value(i);
if (hi < h[i]) {
Sol sol(i, h[i]);
while (dq.size() && dq.back().to(sol) <= i)
dq.pop_back();
while (dq.size() >= 2 && dq[dq.size()-2].to(dq.back()) >= dq.back().to(sol))
dq.pop_back();
dq.push_back(sol);
}
hi = max(hi, h[i]);
}
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

cin>>n;
for (int i = 0; i < N; i++)
sqr[i] = sqrt(i);
for (int i = 0; i < n; i++)
cin>>h[i];

solve(L);
reverse(h, h+n);
solve(R);
reverse(h, h+n);
reverse(R, R+n);

stringstream ss;
for (int i = 0; i < n; i++)
ss << max(0, max(L[i],R[i])-h[i]) << endl;
cout << ss.str();

return 0;
}
```

### Compilation message

```pio.cpp: In member function 'int Sol::to(Sol&)':
pio.cpp:18:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = lo+hi>>1;
~~^~~```

#### Subtask #1 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4216 KB Output is correct

#### Subtask #2 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4216 KB Output is correct

#### Subtask #3 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4216 KB Output is correct

#### Subtask #4 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5620 KB Output is correct

#### Subtask #5 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6540 KB Output is correct

#### Subtask #6 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6108 KB Output is correct
2 Correct 21 ms 6108 KB Output is correct
3 Correct 29 ms 7128 KB Output is correct

#### Subtask #7 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6892 KB Output is correct
2 Correct 33 ms 7640 KB Output is correct
3 Correct 39 ms 9068 KB Output is correct

#### Subtask #8 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 10400 KB Output is correct
2 Correct 63 ms 11888 KB Output is correct
3 Correct 79 ms 13172 KB Output is correct

#### Subtask #9 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 18876 KB Output is correct
2 Correct 95 ms 12672 KB Output is correct
3 Correct 118 ms 19008 KB Output is correct

#### Subtask #10 9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 24984 KB Output is correct
2 Correct 132 ms 16216 KB Output is correct
3 Correct 162 ms 25044 KB Output is correct

#### Subtask #11 10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 17768 KB Output is correct
2 Correct 128 ms 21096 KB Output is correct
3 Correct 164 ms 27988 KB Output is correct