oj.uz

답안 #248660

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
248660 2020-07-13T01:19:37 Z thecodingwizard Lightning Conductor (POI11_pio) C++11
45 / 100
 140 ms 15608 KB 
#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9+10;

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

int n; 
int mx[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
int intersectRight(func a, func b) {
    if (eval(a, n-1) >= eval(b, n-1)) 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 long ans = ceil(x*x)+b.i;
    assert(ans < n && ans >= 0);
    return ans;
}

void solveRight(int mx[]) {
    stack<func> s;
    for (int i = 0; i < n; i++) {
        func f = {H[i], i, 0, 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 <= f2.l) {
                s.pop();
                /*
                s.top().r = f.l-1;
                break;
                */
            } else {
                if (intersect - 1 <= n-1) s.top().r = intersect - 1;
                f.l = intersect;
                break;
            }
        }
        if (f.l <= n-1) s.push(f);
        //assert(f.l >= i);
    }
    while (!s.empty()) {
        func f = s.top(); s.pop();
        //cout << f.i << " is max from " << f.l << " to " << f.r << endl;
        for (int i = max(f.l,0); i <= f.r; i++) mx[i] = max(mx[i], eval(f, i));
    }
    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]; mx[i] = 0;
    }
    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
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1152 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1664 KB Output is correct

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1696 KB Output is correct
2 Correct 18 ms 1656 KB Output is correct
3 Incorrect 16 ms 2304 KB Output isn't correct

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 2296 KB Output is correct
2 Correct 24 ms 2296 KB Output is correct
3 Incorrect 22 ms 2944 KB Output isn't correct

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 4984 KB Output is correct
2 Correct 61 ms 4856 KB Output is correct
3 Incorrect 61 ms 5500 KB Output isn't correct

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 9336 KB Output is correct
2 Correct 92 ms 7244 KB Output is correct
3 Incorrect 78 ms 9340 KB Output isn't correct

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 136 ms 13188 KB Output is correct
2 Correct 140 ms 10160 KB Output is correct
3 Incorrect 128 ms 15352 KB Output isn't correct

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 10748 KB Output is correct
2 Correct 120 ms 12668 KB Output is correct
3 Incorrect 108 ms 15608 KB Output isn't correct