Submission #332753

#	Time	Username	Problem	Language	Result	Execution time	Memory
332753		shivam_327	Lightning Conductor (POI11_pio)	C++14	100 / 100	246 ms	20060 KiB

pio

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10