/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author Miguel Mini
*/
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <complex>
#include <climits>
#include <iomanip>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
#define mset(m ,v) memset(m, v, sizeof(m))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
const int mod = 1e9 + 7;
int add(int a, int b, int m=mod) {
return a+b < mod? a+b : a+b-mod;
}
int mul(ll a, ll b, int m=mod) {
return a*b%mod;
}
int ex(int a, int b, int m=mod) {
int r=1;
while (r > 0) {
if (b&1) r = mul(r, a);
a = mul(a, a);
b >>= 1;
}
return r;
}
const int inf = 1.2e9;
const int maxn = 5e5 + 10;
struct Node {
int x, y;
};
deque<Node> lower;
int eval(Node p, int x) {
return p.y + ceil(sqrt(abs(p.x - x)));
}
bool is_left(Node o, Node a, Node b) {
ll alpha_x = a.x - o.x;
ll alpha_y = a.y - o.y;
ll beta_x = b.x - o.x;
ll beta_y = b.y - o.y;
return alpha_x * beta_y - alpha_y * beta_x <= alpha_y * beta_y * (beta_y - alpha_y);
}
void add(Node p) {
int n = lower.size();
while ((n >= 1 && eval(lower[n-1], p.x) <= p.y) || (n >= 2 && is_left(lower[n-2], lower[n-1], p))) {
lower.pop_back();
n -= 1;
}
lower.push_back(p);
}
int get(int x) {
while (sz(lower) >= 2 && eval(lower[0], x) <= eval(lower[1], x)) {
lower.pop_front();
}
return eval(lower[0], x);
}
class POI_11_conductor {
public:
void solveOne(istream& in, ostream& out) {
int n;
in >> n;
vi h(n);
re(i, 0, n) {
in >> h[i];
}
vi ans = h;
re(i, 0, n) {
add({i, h[i]});
ans[i] = max(ans[i], get(i));
}
reverse(all(ans));
reverse(all(h));
lower.clear();
re(i, 0, n) {
add({i, h[i]});
ans[i] = max(ans[i], get(i));
}
reverse(all(ans));
reverse(all(h));
re(i, 0, n) {
out << ans[i] - h[i] << '\n';
}
}
void solve(istream& in, ostream& out) {
out.precision(10);
out << fixed;
int testNumber = 1;
//in >> testNumber;
re(tc, 1, testNumber+1) {
//out << "Case #" << tc << ": ";
solveOne(in, out);
}
}
};
int main() {
//freopen("in", "r", stdin);
//freopen("out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
POI_11_conductor solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
1912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
31 ms |
1784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
49 ms |
2552 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
101 ms |
5496 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
10012 KB |
Output is correct |
2 |
Correct |
129 ms |
7928 KB |
Output is correct |
3 |
Incorrect |
140 ms |
8696 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
14016 KB |
Output is correct |
2 |
Correct |
202 ms |
11176 KB |
Output is correct |
3 |
Incorrect |
193 ms |
12280 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
201 ms |
11640 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |