oj.uz

답안 #251056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251056 2020-07-20T02:54:12 Z puyu_liao Lightning Conductor (POI11_pio) C++14
27 / 100
 134 ms 17144 KB 
#include<bits/stdc++.h>
using namespace std;
#define int int64_t
const int N = 500005;
int h[N],ans[N];
int ftable[N];

int f(int i,int j){
    return ftable[abs(i-j)];
}

struct segment{
    int i,l,r;
};

void solve(int n){
    vector<segment> v;
    v.push_back({1,1,n});
    for(int i=2;i<=n;i++){
        segment now; now.i = i; now.l = i; now.r = n;
        if(h[v.back().i] + f(v.back().i,n) >= h[i] + f(i,n)) {
            continue;
        }
        auto pre = v.back();
        int l = now.l, r = pre.r;
        while(l != r){
            int m = l+r >> 1;
            if(h[pre.i] + f(pre.i,m) > h[i] + f(i,m)) l=m+1;
            else r = m;
        }
        now.l = l;
        v[v.size()-1].r = l-1;
        v.push_back(now);
    }
    for(auto i : v) for(int j=i.l;j<=i.r;j++) ans[j] = max(ans[j],h[i.i] + f(i.i,j));
}

int32_t main(){
    cin.tie(0); ios_base::sync_with_stdio(false);
    for(int i=1,now=1;i<N;i++){
        if(now*now<i) now++;
        ftable[i] = now;
        //if(i<10)cout << i << ' ' << ftable[i] << '\n';
    }
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    solve(n);
    reverse(h+1,h+n+1);
    reverse(ans+1,ans+n+1);
    solve(n);
    reverse(ans+1,ans+n+1);
    reverse(h+1,h+n+1);
    for(int i=1;i<=n;i++) cout << ans[i] - h[i] << '\n'; //cout << '\n';
    // for(int i=1;i<=n;i++){
    //     int mx = 0;
    //     for(int j=1;j<=n;j++) mx = max(mx,h[j]+f(i,j));
    //     cout << mx-h[i] << ' ';
    // }cout << '\n';
}

Compilation message

pio.cpp: In function 'void solve(int64_t)':
pio.cpp:27:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m = l+r >> 1;
                     ~^~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4224 KB Output isn't correct

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4224 KB Output isn't correct

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 5632 KB Output is correct
2 Correct 13 ms 5504 KB Output is correct
3 Incorrect 25 ms 5760 KB Output isn't correct

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 6264 KB Output is correct
2 Correct 24 ms 6272 KB Output is correct
3 Incorrect 26 ms 6776 KB Output isn't correct

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 8952 KB Output is correct
2 Correct 59 ms 8824 KB Output is correct
3 Incorrect 65 ms 9464 KB Output isn't correct

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 13304 KB Output is correct
2 Correct 82 ms 11132 KB Output is correct
3 Incorrect 86 ms 13304 KB Output isn't correct

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 119 ms 17016 KB Output is correct
2 Correct 114 ms 14200 KB Output is correct
3 Incorrect 134 ms 17144 KB Output isn't correct

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 14584 KB Output is correct
2 Correct 120 ms 14072 KB Output is correct
3 Incorrect 125 ms 17144 KB Output isn't correct