oj.uz

Submission #332753

# Submission time Handle Problem Language Result Execution time Memory
332753 2020-12-03T07:37:35 Z shivam_327 Lightning Conductor (POI11_pio) C++14
100 / 100
 246 ms 20060 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;

int n, a[N];
double f[N], ans[N];

void cdq(int l, int r, int L, int R) {
    int MID = (L+R)>>1, mid, loc = MID;
    if (r < loc) loc = r;
    mid = loc; f[MID] = sqrt(1.*MID-loc)+a[loc]-a[MID];
    for (int i = l; i < loc; i++)
        if (a[i]-a[MID]+sqrt(1.*MID-i) >= f[MID])
            mid = i, f[MID] = sqrt(1.*MID-i)+a[i]-a[MID];
    if (L < MID) cdq(l, mid, L, MID-1);
    if (MID < R) cdq(mid, r, MID+1, R);
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    cdq(1, n, 1, n);
    swap(ans, f);
    reverse(a+1, a+n+1);
    cdq(1, n, 1, n);
    for (int i = 1; i <= n; i++)
        printf("%d\n", int(ceil(max(ans[i], f[n-i+1]))));
    return 0;
}

Compilation message

pio.cpp: In function 'int main()':
pio.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
pio.cpp:20:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8172 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8172 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8812 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 9344 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9324 KB Output is correct
2 Correct 30 ms 8812 KB Output is correct
3 Correct 32 ms 9324 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 10012 KB Output is correct
2 Correct 47 ms 9964 KB Output is correct
3 Correct 57 ms 10112 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 12524 KB Output is correct
2 Correct 103 ms 12012 KB Output is correct
3 Correct 98 ms 12012 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 16364 KB Output is correct
2 Correct 154 ms 14444 KB Output is correct
3 Correct 151 ms 15084 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 20060 KB Output is correct
2 Correct 220 ms 17004 KB Output is correct
3 Correct 210 ms 18028 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 17516 KB Output is correct
2 Correct 246 ms 17004 KB Output is correct
3 Correct 210 ms 18028 KB Output is correct