oj.uz

답안 #678454

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678454 2023-01-06T03:34:16 Z browntoad Lightning Conductor (POI11_pio) C++14
63 / 100
 1000 ms 50244 KB 
#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

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

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 7096 KB Output is correct
2 Correct 98 ms 6576 KB Output is correct
3 Correct 98 ms 7088 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 10528 KB Output is correct
2 Correct 289 ms 10656 KB Output is correct
3 Correct 273 ms 10700 KB Output is correct

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 23144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1047 ms 35356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1008 ms 50152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1061 ms 50244 KB Time limit exceeded
2 Halted 0 ms 0 KB -