oj.uz

Submission #97446

# Submission time Handle Problem Language Result Execution time Memory
97446 2019-02-16T06:27:58 Z aquablitz11 Lightning Conductor (POI11_pio) C++14
100 / 100
 274 ms 14072 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1144 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1712 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1784 KB Output is correct
2 Correct 19 ms 1280 KB Output is correct
3 Correct 27 ms 1784 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2488 KB Output is correct
2 Correct 52 ms 2524 KB Output is correct
3 Correct 53 ms 2680 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5496 KB Output is correct
2 Correct 75 ms 4992 KB Output is correct
3 Correct 134 ms 5152 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 10024 KB Output is correct
2 Correct 120 ms 7936 KB Output is correct
3 Correct 128 ms 8568 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 14072 KB Output is correct
2 Correct 249 ms 11220 KB Output is correct
3 Correct 258 ms 12024 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 11692 KB Output is correct
2 Correct 261 ms 11384 KB Output is correct
3 Correct 242 ms 12104 KB Output is correct