Submission #251091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251091	2020-07-20T06:22:39 Z	puyu_liao	Lightning Conductor (POI11_pio)	C++14	100 / 100	139 ms	20996 KB

pio

#include<bits/stdc++.h>
using namespace std;
#define int int64_t
const int N = 500005;
int h[N],ans[N];
int ftable[N];
double ftable2[N];
 
double f2(int i,int j){
    return ftable2[abs(i-j)];
}
 
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;
        //cout << i << " : "; for(auto i : v) cout << i.i << ' ' << complex<int>(i.l,i.r) << ' '; cout << '\n';
        while(now.l <= v.back().l && h[v.back().i] + f2(v.back().i,v.back().l) <= h[i] + f2(i,v.back().l)
        && h[v.back().i] + f2(v.back().i,v.back().r) <= h[i] + f2(i,v.back().r)){
            v.pop_back();
        }
        //cout << i << " : "; for(auto i : v) cout << i.i << ' ' << complex<int>(i.l,i.r) << ' '; cout << '\n';
        //cout << i << " : " << h[v.back().i] + f2(v.back().i,v.back().r) << ' ' << h[i] + f2(i,v.back().r) << '\n';
        if(h[v.back().i] + f2(v.back().i,v.back().r) >= h[i] + f2(i,v.back().r)) {
            if(v.back().r != n) v.push_back({now.i,v.back().r+1,now.r});
            continue;
        }
        auto pre = v.back();
        int l = max(v.back().l,now.l), r = v.back().r;
        //cout << i << " : " << l << ' ' << r << '\n';
        while(l < r){
            int m = l+r >> 1;
            if(h[pre.i] + f2(pre.i,m) > h[i] + f2(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;
      	ftable2[i] = sqrt(i);
        //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:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int m = l+r >> 1;
                     ~^~

Subtask #1

9.0 / 9.0

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

Subtask #2

9.0 / 9.0

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

Subtask #3

9.0 / 9.0

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

Subtask #4

9.0 / 9.0

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

Subtask #5

9.0 / 9.0

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

Subtask #6

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	9468 KB	Output is correct
2	Correct	17 ms	9596 KB	Output is correct
3	Correct	22 ms	9728 KB	Output is correct

Subtask #7

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	10188 KB	Output is correct
2	Correct	31 ms	10104 KB	Output is correct
3	Correct	30 ms	10744 KB	Output is correct

Subtask #8

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	12860 KB	Output is correct
2	Correct	60 ms	12664 KB	Output is correct
3	Correct	53 ms	13304 KB	Output is correct

Subtask #9

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	96 ms	17144 KB	Output is correct
2	Correct	89 ms	15224 KB	Output is correct
3	Correct	87 ms	17144 KB	Output is correct

Subtask #10

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	139 ms	20984 KB	Output is correct
2	Correct	127 ms	18040 KB	Output is correct
3	Correct	113 ms	20984 KB	Output is correct

Subtask #11

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	129 ms	18552 KB	Output is correct
2	Correct	126 ms	18056 KB	Output is correct
3	Correct	128 ms	20996 KB	Output is correct