oj.uz

Submission #639821

# Submission time Handle Problem Language Result Execution time Memory
639821 2022-09-11T23:54:42 Z ggoh 케이크 (JOI13_cake) C++14
100 / 100
 364 ms 31548 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 5 ms 724 KB Output is correct
4 Correct 5 ms 632 KB Output is correct
5 Correct 4 ms 768 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 624 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 7088 KB Output is correct
2 Correct 89 ms 6984 KB Output is correct
3 Correct 102 ms 7116 KB Output is correct
4 Correct 249 ms 14808 KB Output is correct
5 Correct 210 ms 13472 KB Output is correct
6 Correct 312 ms 21168 KB Output is correct
7 Correct 364 ms 22516 KB Output is correct
8 Correct 330 ms 21292 KB Output is correct
9 Correct 326 ms 21196 KB Output is correct
10 Correct 351 ms 21188 KB Output is correct
11 Correct 317 ms 21964 KB Output is correct
12 Correct 292 ms 23044 KB Output is correct
13 Correct 344 ms 31548 KB Output is correct
14 Correct 196 ms 21228 KB Output is correct
15 Correct 320 ms 22648 KB Output is correct