#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;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
3608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
5732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1080 ms |
23144 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1047 ms |
35356 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1008 ms |
50152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
50244 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
