# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29565 | 2017-07-20T06:23:00 Z | 윤교준(#1243) | Lightning Conductor (POI11_pio) | C++11 | 473 ms | 13256 KB |
#include <bits/stdc++.h> #define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15); #define pb push_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define befv(V) ((V)[sz(V)-2]) #define sorv(V) sort(allv(V)) #define revv(V) reverse(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define rgiv(V,n) ((V)[((n)+sz(V))%sz(V)]) #define clv(V) (V).clear() #define upmax(a,b) (a)=max((a),(b)) #define INF (0x3f3f3f3f) #define MAXN (500005) #define MAXH (1000005) using namespace std; typedef long long ll; typedef pair<int, int> pii; static unsigned char str[5500055], *p = str; int SQ[MAXN]; int HL[777], HR[777]; int H[MAXN]; int P[MAXN]; int N; int main() { fread(str, 1, 5500055, stdin); for(int i = 1; i <= 708; i++) { int s = (i-1)*(i-1) + 1, e = min(MAXN-1, i*i); for(int j = s; j <= e; j++) SQ[j] = i; } rf(N) int mxh = -1; for(int i = 1; i <= N; i++) { rf(H[i]) if(mxh < H[i]) mxh = H[i]; } int mnh = max(0, mxh-708), dh = mxh - mnh; for(int i = 1, h; i <= N; i++) { if(H[i] < mnh) continue; h = H[i] - mnh; if(!HL[h]) HL[h] = i; HR[h] = i; } for(int i = HL[dh]; i <= N; i++) P[i] = mxh + SQ[i - HL[dh]]; for(int i = HR[dh], h; i; i--) { h = mxh + SQ[HR[dh] - i]; if(P[i] < h) P[i] = h; } for(int h = dh-1, x = HR[dh]; ~h; h--) { if(HR[h] <= x) continue; x = HR[h]; for(int i = HR[h]-1, t; i; i--) { t = h + mnh + SQ[HR[h] - i]; if(P[i] < t) P[i] = t; } } for(int h = dh-1, x = HL[dh]; ~h; h--) { if(!HL[h] || x <= HL[h]) continue; x = HL[h]; for(int i = HL[h]+1, t; i <= N; i++) { t = h + mnh + SQ[i - HL[h]]; if(P[i] < t) P[i] = t; } } for(int i = 1; i <= N; i++) printf("%d\n", P[i] - H[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 13256 KB | Output is correct |
2 | Correct | 6 ms | 13256 KB | Output is correct |
3 | Correct | 29 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 13256 KB | Output is correct |
2 | Correct | 6 ms | 13256 KB | Output is correct |
3 | Correct | 39 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 26 ms | 13256 KB | Output is correct |
2 | Correct | 23 ms | 13256 KB | Output is correct |
3 | Correct | 116 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 13256 KB | Output is correct |
2 | Correct | 53 ms | 13256 KB | Output is correct |
3 | Correct | 229 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 63 ms | 13256 KB | Output is correct |
2 | Correct | 56 ms | 13256 KB | Output is correct |
3 | Correct | 473 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 13256 KB | Output is correct |
2 | Correct | 59 ms | 13256 KB | Output is correct |
3 | Correct | 456 ms | 13256 KB | Output is correct |