Submission #97446

#	Time	Username	Problem	Language	Result	Execution time	Memory
97446		aquablitz11	Lightning Conductor (POI11_pio)	C++14	100 / 100	274 ms	14072 KiB

pio

#include <bits/stdc++.h>
using namespace std;

const int N = 1<<19;
const int inf = 2e9;

struct curve {
    int idx, val;
    curve() {}
    curve(int idx, int val) : idx(idx), val(val) {}
    double eval(int x) {
        if (x < idx) return -inf;
        return val+sqrt(x*1.0-idx);
    }
};

int n, H[N], ans[N];
bool vis[N<<1];
curve C[N<<1];

void update(curve f, int p=1, int b=1, int e=n) {
    if (!vis[p]) {
        vis[p] = true;
        C[p] = f;
        return;
    }
    int m = (b+e)/2;
    if (f.eval(m) > C[p].eval(m))
        swap(f, C[p]);
    bool pb = f.eval(b) > C[p].eval(b);
    bool pe = f.eval(e) > C[p].eval(e);
    if (pb == pe) return;
    if (pb) update(f, p<<1, b, m);
    else update(f, p<<1|1, m+1, e);
}

int query(int x, int p=1, int b=1, int e=n) {
    if (!vis[p]) return -inf;
    int m = (b+e)/2;
    return max((int)ceil(C[p].eval(x)), x <= m ?
        query(x, p<<1, b, m) : query(x, p<<1|1, m+1, e));
}

void clear(int p=1) {
    if (!vis[p]) return;
    vis[p] = false;
    clear(p<<1);
    clear(p<<1|1);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &H[i]);
        update(curve(i, H[i]));
        ans[i] = query(i)-H[i];
    }
    clear();
    for (int i = n; i >= 1; --i) {
        update(curve(n-i+1, H[i]));
        ans[i] = max(ans[i], query(n-i+1)-H[i]);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    
    return 0;
}

Compilation message (stderr)

pio.cpp: In function 'int main()':
pio.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
pio.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &H[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