#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define sz(v) (int)v.size()
#define MOO(i, a, b) for(int i=a; i<b; i++)
#define M00(i, a) for(int i=0; i<a; i++)
#define MOOd(i,a,b) for(int i = (b)-1; i >= a; i--)
#define M00d(i,a) for(int i = (a)-1; i>=0; i--)
#define FAST ios::sync_with_stdio(0); cin.tie(0);
#define finish(x) return cout << x << '\n', 0;
#define dbg(x) cerr << ">>> " << #x << " = " << x << "\n";
#define _ << " _ " <<
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<ld,ld> pd;
typedef complex<ld> cd;
const int MAX_N = 500500;
int n;
ld eval(ld x, pair<ll,ll> curve) {
return curve.s + pow(curve.f - x, 0.5);
}
ll evalLong(ll x, pair<ll,ll> curve) { // ceil(eval(x, curve))
ld y = eval(x,curve);
ll y1 = y;
if((y1-curve.s)*(y1-curve.s) >= curve.f-x) return y1;
return y1+1;
}
ll intersect(pair<ll,ll> c1, pair<ll,ll> c2) { // c2 comes after c1
if(eval(c1.f, c2) <= c1.s) return c1.f;
if(eval(0, c2) >= eval(0, c1)) return -1;
ll lo = 0;
ll hi = c1.f;
while(hi-lo > 1) {
ll mid = (lo + hi)/2;
if(evalLong(mid, c1) < evalLong(mid, c2)) {
hi = mid;
} else {
lo = mid;
}
}
return lo;
}
vector<ll> solve(vector<ll> v) {
deque<pair<ll,ll>> dq;
MOO(i, 1, n) {
pair<ll,ll> curve = mp(i, v[i]);
while(1) {
if(dq.empty()) break;
else if(intersect(dq[sz(dq)-1], curve) < 0) dq.pop_back();
else {
if(sz(dq) >= 2) {
if(intersect(dq[sz(dq)-2], curve) < intersect(dq[sz(dq)-2], dq[sz(dq)-1])) {
dq.pop_back();
} else {
break;
}
} else {
break;
}
}
}
dq.pb(curve);
}
vector<ll> ans;
M00(i, n-1) {
while(dq[0].f <= i) dq.pop_front();
while(sz(dq) >= 2 && eval(i, dq[1]) > eval(i, dq[0])) dq.pop_front();
ans.pb(max(0LL,evalLong(i, dq[0])-v[i]));
}
ans.pb(-1);
return ans;
}
int main() { FAST
cin >> n;
vector<ll> arr(n);
M00(i, n) cin >> arr[i];
vector<ll> res1 = solve(arr);
reverse(all(arr));
vector<ll> res2 = solve(arr);
reverse(all(res2));
M00(i, n) {
cout << max(res1[i], res2[i]) << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
265 ms |
1544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
437 ms |
2556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
800 ms |
3208 KB |
Output is correct |
2 |
Correct |
257 ms |
2940 KB |
Output is correct |
3 |
Incorrect |
629 ms |
3448 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1085 ms |
3140 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1078 ms |
3960 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1090 ms |
7156 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1088 ms |
8184 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1092 ms |
8184 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |