Submission #251037

#	Time	Username	Problem	Language	Result	Execution time	Memory
251037		puyu_liao	Lightning Conductor (POI11_pio)	C++14	36 / 100	161 ms	21880 KiB

pio

#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)];
}

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;
    deque<pair<int,int> > dq;
    for(int i=1;i<=n;i++) {
        cin >> h[i];
        while(!dq.empty() && h[i] > dq.back().first + f(i,dq.back().second)) dq.pop_back();
        if(dq.empty() || h[i] > dq[0].first)dq.push_back({h[i],i});
        while(dq.size() >= 2 && dq[0].first + f(i,dq[0].second) < dq[1].first + f(i,dq[1].second)) dq.pop_front();
        ans[i] = dq[0].first + f(i,dq[0].second);
    }
    dq.clear();
    for(int i=n;i>=1;i--){
        while(!dq.empty() && h[i] > dq.back().first + f(i,dq.back().second)) dq.pop_back();
        if(dq.empty() || h[i] > dq[0].first)dq.push_back({h[i],i});
        while(dq.size() >= 2 && dq[0].first + f(i,dq[0].second) < dq[1].first + f(i,dq[1].second)) dq.pop_front();
        ans[i] = max(ans[i],dq[0].first + f(i,dq[0].second));
    }
    for(int i=1;i<=n;i++) cout << ans[i] - h[i] << '\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';
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10