Submission #639821

#	Time	Username	Problem	Language	Result	Execution time	Memory
639821		ggoh	케이크 (JOI13_cake)	C++14	100 / 100	364 ms	31548 KiB

cake

#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;

int n,aa[300003],a[300003],seg[1<<20],rot;
lint ans[300003],sum[300003][2];
void update(int num,int s,int e,int x)
{
  if(s==e)
  {
    seg[num]=x;
    return ;
  }
  if(x<=(s+e)/2)update(num*2,s,(s+e)/2,x);
  else update(num*2+1,(s+e)/2+1,e,x);
  if(a[seg[num*2]]<a[seg[num*2+1]])seg[num]=seg[num*2];
  else seg[num]=seg[num*2+1];
}
int minind(int num,int s,int e,int l,int r)
{
  if(l>r||l>e||s>r)return n;
  if(l<=s&&e<=r)return seg[num];
  int L=minind(num*2,s,(s+e)/2,l,r);
  int R=minind(num*2+1,(s+e)/2+1,e,l,r);
  if(a[L]<a[R])return L;
  else return R;
}
void g(int p,int h,int q)
{
  if(p==q)return ;
  int L=minind(1,1,n-1,p,h-1);
  int R=minind(1,1,n-1,h+1,q);
  if(a[L]<a[R])
  {
    if((q-L)%2)ans[h]+=sum[L][(L-1)%2]-sum[p-1][(L-1)%2];
    else ans[h]+=sum[L][L%2]-sum[p-1][L%2];
    g(L+1,h,q);
  }
  else
  {
    if((R-p)%2)ans[h]+=sum[q][(R+1)%2]-sum[R-1][(R+1)%2];
    else ans[h]+=sum[q][R%2]-sum[R-1][R%2];
    g(p,h,R-1);
  }
}
void f(int p,int q,lint tmp)
{
  if(p>q)return ;
  int h=minind(1,1,n-1,p,q);
  ans[h]+=a[h];
  g(p,h,q);
  ans[h]+=tmp;
  lint left,right;
  if((h-p)%2)right=sum[q][(h+1)%2]-sum[h-1][(h+1)%2];
  else right=sum[q][h%2]-sum[h-1][h%2];
  if((q-h)%2)left=sum[h][(h-1)%2]-sum[p-1][(h-1)%2];
  else left=sum[h][h%2]-sum[p-1][h%2];
  f(p,h-1,tmp+right);
  f(h+1,q,tmp+left);
}
int main()
{
  scanf("%d",&n);
  for(int i=0;i<n;i++)
  {
    scanf("%d",&aa[i]);
    if(aa[i]<aa[rot])rot=i;
  }
  for(int i=0;i<n;i++)a[i]=aa[(i+rot)%n];
  int p=1,q=n-1,cnt=0;
  ans[0]+=a[0];
  while(p<=q)
  {
    if(a[p]>a[q])
    {
      if(cnt%2)ans[0]+=a[p];
      p++;
    }
    else
    {
      if(cnt%2)ans[0]+=a[q];
      q--;
    }
    cnt++;
  }
  sum[0][0]=a[0];
  sum[1][1]=a[1];
  for(int i=3;i<n;i+=2)sum[i][1]=sum[i-2][1]+a[i];
  for(int i=2;i<n;i+=2)sum[i][0]=sum[i-2][0]+a[i];
  for(int i=1;i<n;i++)
  {
    if(n%2)ans[i]+=a[0];
    if(sum[i][0]==0)sum[i][0]=sum[i-1][0];
    if(sum[i][1]==0)sum[i][1]=sum[i-1][1];
  }
  for(int i=1;i<n;i++)update(1,1,n-1,i);
  a[n]=1e9+1;
  f(1,n-1,0);
  for(int i=0;i<n;i++)printf("%lld ",ans[(i-rot+n)%n]);
}

Compilation message (stderr)

cake.cpp: In function 'int main()':
cake.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
cake.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d",&aa[i]);
      |     ~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90