| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 372675 |
2021-03-01T09:38:42 Z |
BJoozz |
케이크 (JOI13_cake) |
C++14 |
|
1500 ms |
37740 KB |
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
//#define int long long
const int MAX = 300000+3,M=(1<<25)+1,mod=1e9+7;
void maxx(int &a,int b) {if(b>a) a=b;}
void minn(int &a,int b) {if(b<a) a=b;}
using ii = pair < int ,int > ;
using ll = long long;
int a[MAX];
ll B[MAX][2];
int ST[MAX][20];
ll ans[MAX];
int minu(int i,int j){
if(a[i]<a[j]) return i;
else return j;
}
int n;
int LG[MAX];
int id(int u){
return (u+n-1)%n+1;
}
int get(int l,int r){
int u=r-l+1;
if(r<l)u+=n;
u=LG[u];
return minu(ST[l][u],ST[id(r-(1<<u)+1)][u]);
}
bool tt;
ll getsum(bool x,int l,int r){
if(r>=l) return B[r][x]-B[l-1][x];
else return B[n][x]-B[l-1][x]+B[r][x^tt];
}
ll getsum2(bool x,int l,int r){
if(r>=l) return B[r][x]-B[l-1][x];
else return B[n][x^tt]-B[l-1][x^tt]+B[r][x];
}
int H;
int dis(int L,int R){
if(R>=L) return R-L+1;
else return R-L+1+n;
}
int getdown(int x,int u,int val){
//if(a[u]<val) return u;
for(int z=LG[dis(x,u)];z>=0;z--)
if(a[ ST[id(u-(1<<z))][z] ]>=val ) {
u=id(u-(1<<z));
}
return u;
}
int getup(int x,int u,int val){
for(int z=LG[dis(u,x)];z>=0;z--)
if(a[ ST[id(u+1)][z] ]>=val ) {
u=id(u+(1<<z));
}
return u;
}
ll cos(int z,int L,int R){
ll res=a[z];
int i=id(z-1),j=id(z+1);
bool ok=1;
while(i!=L && j!=R){
//cout<<i<<' '<<j<<'\n';
//if(a[j]<a[i]) {if(!ok) res+=a[i];i=id(i-1);ok^=1;continue;}
if(a[i]<a[j]){
int m=getup(R,j,a[i]);
res+=getsum((ok^j)&1,j,m);
ok^=dis(j,m)&1;
j=id(m+1);
}
else{
int m=getdown(L,i,a[j]);
res+=getsum2((ok^i)&1,m,i);
ok^=dis(m,i)&1;
i=id(m-1);
}
}
while(j!=R){
if(!ok) res+=a[j];
ok^=1;
j=id(j+1);
}
while(i!=L){
if(!ok) res+=a[i];
ok^=1;
i=id(i-1);
}
return res;
}
void GODOWN(int L,int R,ll sum){
if(R==id(L+1))return;
int z=get(id(L+1),id(R-1));
ans[z]=cos(z,L,R)+sum;
GODOWN(L,z,sum+getsum( (z^tt^((L-z+1+n)%n))&1,z,id(R-1) ));
GODOWN(z,R,sum+getsum2( (z^tt^((z-R+1+n)%n))&1,id(L+1),z ));
}
signed main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("A.inp", "r", stdin);freopen("A.out", "w", stdout);
LG[1]=0;
for(int i=2;i<MAX;i++) LG[i]=LG[i/2]+1;
cin>>n;
H=LG[n];
if(H>=17) H--;
for(int i=1;i<=n;i++){
cin>>a[i];
ST[i][0]=i;
B[i][0]=B[i-1][0];
B[i][1]=B[i-1][1];
B[i][i%2]+=a[i];
}
for(int j=1;j<20;j++){
for(int i=1;i<=n;i++){
ST[i][j]=minu(ST[i][j-1],ST[id(i+(1<<j-1))][j-1]);
}
}
int u1=ST[1][19];
int u2=get(id(u1+1),id(u1-1));
ll &res = ans[u1];
tt=n&1;
res=cos(u1,u2,u2);//return 0;
if(tt) res+=a[u2];
if(tt) GODOWN(u1,u1,a[u1]);
else GODOWN(u1,u1,0);
for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
}
Compilation message
cake.cpp: In function 'int main()':
cake.cpp:124:51: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
124 | ST[i][j]=minu(ST[i][j-1],ST[id(i+(1<<j-1))][j-1]);
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2156 KB |
Output is correct |
| 2 |
Correct |
69 ms |
2156 KB |
Output is correct |
| 3 |
Correct |
18 ms |
2156 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2156 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2412 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2156 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2156 KB |
Output is correct |
| 8 |
Correct |
12 ms |
2284 KB |
Output is correct |
| 9 |
Correct |
1 ms |
1516 KB |
Output is correct |
| 10 |
Correct |
1 ms |
1516 KB |
Output is correct |
| 11 |
Correct |
1 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
648 ms |
13804 KB |
Output is correct |
| 2 |
Correct |
69 ms |
13804 KB |
Output is correct |
| 3 |
Correct |
695 ms |
13932 KB |
Output is correct |
| 4 |
Correct |
157 ms |
30060 KB |
Output is correct |
| 5 |
Correct |
169 ms |
25836 KB |
Output is correct |
| 6 |
Correct |
271 ms |
37740 KB |
Output is correct |
| 7 |
Execution timed out |
1576 ms |
31212 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
