Submission #678454

#	Time	Username	Problem	Language	Result	Execution time	Memory
678454		browntoad	Lightning Conductor (POI11_pio)	C++14	63 / 100	1080 ms	50244 KiB

pio

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define SQ(x) (x)*(x)
#define f first
#define s second
#define pii pair<int, int>
#define endl '\n'
#define pb push_back

const ll mod = 1e9+7;
const ll maxn = 5e5+5;
const ll inf = (1ll<<60);
const ll iinf = 2e9;

ll pw(ll x, ll p){
    ll ret=1;
    while(p>0){
        if (p&1){
            ret*=x;
            ret%=mod;
        }
        x*=x;
        x%=mod;
        p>>=1;
    }
    return ret;
}
ll inv(ll x){
    return pw(x, mod-2);
}

int sparse[maxn][21];
int res[maxn], arr[maxn];
int b[maxn];
int Bloc[maxn], Dis[maxn];
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin>>n;
    int bloc, dis;
    REP1(i, n){
        cin>>arr[i];
        res[i]=arr[i];
    }
    RREP1(i, n){
        sparse[i][0]=arr[i];
        REP1(j, 20){
            sparse[i][j]=max(sparse[i][j-1], sparse[min(n, i+(1<<(j-1)))][j-1]);
        }
    }
    int cmx=0, floc;
    for (int i=1;;i++){
        bloc=i*i-(i-1)*(i-1);
        dis=(i-1)*(i-1)+1;
        for (int j=0; j<21; j++){
            if ((1<<j)<=bloc) floc=j;
        }
        b[i]=floc;
        Bloc[i]=bloc;
        Dis[i]=dis;
        if (dis>=n) break;
        cmx=0;
        for (int j=1; j<bloc&&j<=n; j++){
            cmx=max(cmx, arr[j]);
            if (j+dis>n) break;
            res[j+dis]=max(res[j+dis], cmx+i);
        }
        cmx=0;
        for (int j=n; j>=1&&n-j<bloc-1; j--){
            cmx=max(cmx, arr[j]);
            if (j-dis<=0) break;
            res[j-dis]=max(res[j-dis], cmx+i);
        }
        for (int j=1; j<=n&&j+bloc-1<=n; j++){
            if (j-dis>=1) res[j-dis]=max(res[j-dis], sparse[j][floc]+i);
            if (j+dis+bloc-1<=n) res[j+dis+bloc-1]=max(res[j+dis+bloc-1], sparse[j][floc]+i);
        }
    }
    REP1(i, n){
        sparse[i][0]=arr[i];
        REP1(j, 20){
            sparse[i][j]=max(sparse[i][j-1], sparse[max(1, i-(1<<(j-1)))][j-1]);
        }
    }
    for (int i=1;;i++){
        if (Dis[i]>=n) break;
        for (int j=1; j<=n&&j+Bloc[i]-1<=n; j++){
            if (j-Dis[i]>=1) res[j-Dis[i]]=max(res[j-Dis[i]], sparse[j+Bloc[i]-1][b[i]]+i);
            if (j+Dis[i]+Bloc[i]-1<=n) res[j+Dis[i]+Bloc[i]-1]=max(res[j+Dis[i]+Bloc[i]-1], sparse[j+Bloc[i]-1][b[i]]+i);
        }
    }
    REP1(i, n){
        cout<<res[i]-arr[i]<<endl;
    }
}

Compilation message (stderr)

pio.cpp: In function 'int main()':
pio.cpp:60:16: warning: 'floc' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |     int cmx=0, floc;
      |                ^~~~

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