Submission #248696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
248696	2020-07-13T07:39:14 Z	thecodingwizard	Lightning Conductor (POI11_pio)	C++11	100 / 100	141 ms	13256 KB

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9+10;

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

int n; 
int mx1[500000];
int mx2[500000];
int H[500000];
int Sqrt[500000];

int eval(func f, int i) {
    return f.h+Sqrt[abs(i-f.i)];
    assert(i>=f.i);
    return f.h+Sqrt[i-f.i];
}

// returns when right part of func a intersects func b
long double intersectRight(func a, func b) {
    if (a.h>=b.h) return inf;
    long long d = b.h-a.h;
    if (b.i-a.i-d*d<0) return -1;
    long double x = (b.i-a.i)/2.0/d-d/2.0;
    long double ans = x*x+b.i;
    //assert(ans < n && ans >= 0);
    //assert(eval(a, ans) == eval(b, ans));
    return ans;
}

void solveRight(int mx[]) {
    vector<func> s;
    for (int i = 0; i < n; i++) {
        func f = {H[i], i, 0, (long double)n-1};
        while (!s.empty()) {
            func f2 = s.back();
            long double intersect = intersectRight(f2, f);
            //cout << f2.i << " intersects " << f.i << " at " << intersect << endl;
            if (intersect <= f2.l) {
                s.pop_back();
                /*
                s.top().r = f.l-1;
                break;
                */
            } else {
                if (intersect <= n-1) s.back().r = intersect;
                f.l = intersect;
                break;
            }
        }
        if (f.l <= n-1) s.push_back(f);
        //assert(f.l >= i);
    }
    //for (func f : s) cout << f.i << " " << f.l << " " << f.r << "\n";
    while (!s.empty()) {
        func f = s.back(); s.pop_back();
        assert(f.l >= 0 && f.r <= n-1);
        //cout << f.i << " is max from " << f.l << " to " << f.r << endl;
        for (int i = ceil(f.l); i <= floor(f.r); i++) {
            //cout << i << " = " << f.i << " (" << eval(f, i) << ")" << "\n";
            mx[i] = max(mx[i], eval(f, i));
            /*
            for (int j = 0; j <= i; j++) {
                if (eval({H[j],j,0,n-1}, i) > mx[i]) {
                    cout << "Eval: " << eval({H[j],j,0,n-1}, i) << " better than " << mx[i] << endl;
                    cout << j << " " << i << endl;
                }
            }
            */
        }
    }
    /*
    for (int i = 0; i < n; i++) {
        cout << "mx[" << i << "] = " << mx[i] << endl;
    }
    */
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    Sqrt[0] = 0;
    for (int i = 1; i <= 1000; i++) {
        for (int j = (i-1)*(i-1)+1; j <= min(i*i, n-1); j++) Sqrt[j] = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> H[i]; mx1[i] = mx2[i] = 0;
    }
    solveRight(mx1);
    for (int i = 0; i < n/2; i++) {
        swap(H[i], H[n-i-1]);
    }
    solveRight(mx2);
    for (int i = 0; i < n/2; i++) {
        swap(H[i], H[n-i-1]);
    }
    for (int i = 0; i < n; i++) {
        mx1[i] = max(mx1[i], mx2[n-1-i]);
        /*
        for (int j = 0; j < n; j++) {
            if (eval({H[j],j,0,n-1},i)>mx1[i]) {
                cout << j << " " << i << " " << eval({H[j],j,0,n-1},i) << endl;
            }
        }
        */
    }
    for (int i = 0; i < n; i++) {
        cout << mx1[i]-H[i] << "\n";
    }
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1152 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	1792 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	1664 KB	Output is correct
2	Correct	10 ms	1664 KB	Output is correct
3	Correct	15 ms	1920 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	2424 KB	Output is correct
2	Correct	24 ms	2304 KB	Output is correct
3	Correct	23 ms	2936 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	4984 KB	Output is correct
2	Correct	54 ms	4824 KB	Output is correct
3	Correct	61 ms	5496 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	9464 KB	Output is correct
2	Correct	87 ms	7288 KB	Output is correct
3	Correct	94 ms	9360 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	141 ms	13176 KB	Output is correct
2	Correct	122 ms	10232 KB	Output is correct
3	Correct	116 ms	13256 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	125 ms	10744 KB	Output is correct
2	Correct	124 ms	10232 KB	Output is correct
3	Correct	115 ms	13176 KB	Output is correct

Submission #248696

Compilation message