oj.uz

Submission #251037

# Submission time Handle Problem Language Result Execution time Memory
251037 2020-07-20T01:18:24 Z puyu_liao Lightning Conductor (POI11_pio) C++14
36 / 100
 161 ms 21880 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)];
}

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6264 KB Output is correct
2 Correct 16 ms 5752 KB Output is correct
3 Incorrect 19 ms 6144 KB Output isn't correct

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 16664 KB Output is correct
2 Correct 97 ms 14584 KB Output is correct
3 Incorrect 86 ms 15352 KB Output isn't correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 21880 KB Output is correct
2 Correct 146 ms 18936 KB Output is correct
3 Incorrect 143 ms 20088 KB Output isn't correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 19456 KB Output is correct
2 Correct 130 ms 18936 KB Output is correct
3 Incorrect 120 ms 20088 KB Output isn't correct