oj.uz

Submission #248635

# Submission time Handle Problem Language Result Execution time Memory
248635 2020-07-13T00:21:29 Z thecodingwizard Lightning Conductor (POI11_pio) C++11
0 / 100
 409 ms 11512 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9+10;

struct func {
    int h, i, l, r;
};

// returns when right part of func a intersects func b
int intersectRight(func a, func b) {
    if (a.h >= b.h) return inf;
    long long d = b.h-a.h;
    long double x = (double)(b.i-a.i-(long long)d*d)/2/d;
    long long ans = ceil(x*x)+b.i;
    if (ans > inf) return inf;
    return ans;
}

int n; 
int mx[500000];
int mx2[500000];
int H[500000];

void solveRight(int mx[]) {
    stack<func> s;
    for (int i = 0; i < n; i++) {
        func f = {H[i], i, i, n-1};
        while (!s.empty()) {
            func f2 = s.top();
            int intersect = intersectRight(f2, f);
            //cout << f2.i << " intersects " << f.i << " at " << intersect << endl;
            if (intersect < i) {
                s.top().r = i-1;
                break;
            }
            if (intersect <= f2.l) s.pop();
            else {
                if (intersect - 1 <= n-1) s.top().r = intersect - 1;
                f.l = intersect;
                break;
            }
        }
        if (f.l <= n-1) s.push(f);
    }
    while (!s.empty()) {
        func f = s.top(); s.pop();
        //cout << f.i << " is max from " << f.l << " to " << f.r << endl;
        for (int i = f.l; i <= f.r; i++) mx[i] = max(mx[i], f.h+(int)ceil(sqrt(i-f.i)));
    }
    for (int i = 0; i < n; i++) {
        //cout << "mx[" << i << "] = " << mx[i] << endl;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> H[i]; mx[i] = H[i];
    }
    solveRight(mx);
    for (int i = 0; i < n/2; i++) {
        swap(H[i], H[n-i-1]);
    }
    solveRight(mx2);
    for (int i = 0; i < n; i++) {
        mx[i] = max(mx[i], mx2[n-1-i]);
    }
    for (int i = 0; i < n/2; i++) {
        swap(H[i], H[n-i-1]);
    }
    for (int i = 0; i < n; i++) {
        cout << mx[i]-H[i] << "\n";
    }
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1024 KB Output isn't correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 1528 KB Output isn't correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 4392 KB Output is correct
2 Correct 156 ms 4216 KB Output is correct
3 Incorrect 127 ms 4344 KB Output isn't correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 8312 KB Output is correct
2 Correct 258 ms 6264 KB Output is correct
3 Incorrect 200 ms 6776 KB Output isn't correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 409 ms 11512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 8952 KB Output is correct
2 Correct 359 ms 8492 KB Output is correct
3 Incorrect 278 ms 8696 KB Output isn't correct