# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
308598 | shivensinha4 | 새로운 문제 (POI11_pio) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
const int MXV = 1e6, INF = 1e9;
//int rt[MXV+1];
int pos[MXV+2];
//int grt(int p) {
//for_(i, 0, p+1) {
//if (i*i >= p) {
//cout << p << " -> " << i << endl;
//return i;
//}
//}
//return -1;
//}
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
//for_(i, 0, MXV+1) {
//pos[i][0] = INF;
//pos[i][1] = -1;
//}
vi h(n);
int mx = 0;
for_(i, 0, n) {
cin >> h[i];
mx = max(mx, h[i]);
assert(hi[] <= MXV);
//pos[h[i]] = i;
//if (!pos[h[i]].size()) pos[h[i]] = {i, i};
//pos[h[i]][0] = min(pos[h[i]][0], i);
//pos[h[i]][1] = max(pos[h[i]][1], i);
}
//int r = 0, sq = 0;
//for_(i, 0, mx+1) {
//rt[i] = r;
//if (i == sq) {
//r += 1;
//sq = r*r;
//}
//}
//vi poss;
//for (int i = mx; i >= max(mx-710, 0); i--) if (pos[i].size()) {
//poss.push_back(i);
//}
for_(i, 0, n) {
int ans = h[i];
//for (int v = mx; v >= max(mx-710, 0); v--) if (pos[v][0] != INF) ans = max({ans, v + rt[abs(pos[v][0] - i)], v + rt[abs(pos[v][1] - i)]});
//for (int v = mx; v >= max(mx-710, 0); v--) if (pos[v][0] != INF) ans = max({ans, v + grt(abs(pos[v][0] - i)), v + grt(abs(pos[v][1] - i))});
//for (int v = mx; v >= max(mx-710, 0); v--) if (pos[v][0] != INF) ans = max(ans, 10);
cout << ans-h[i] << endl;
}
return 0;
}