Submission #940544

#	Time	Username	Problem	Language	Result	Execution time	Memory
940544		sleepntsheep	Financial Report (JOI21_financial)	C11	0 / 100	99 ms	16876 KiB

Main

#include<stdio.h>
int hi(int a,int b){return a>b?a:b;}
unsigned X=12345;int rand_(){return(X*=3)>>1;}
int(*compar)(int,int);
void sort(int*aa,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)];
        while(j<k)
            switch(compar(aa[j],p))
            {
                case 0:
                    ++j;
                    break;
                case -1:
                    t=aa[i],aa[i]=aa[j],aa[j]=t;
                    ++i,++j;
                    break;
                case 1:
                    t=aa[--k],aa[k]=aa[j],aa[j]=t;
                    break;
            }
        sort(aa,l,i);
        l=k;
    }
}

#define N 300000
int n,d,a[N],dp[N],aa[N],t[N];

int sv[1<<22][2],svtop,savemode=1,at[1<<22],attop;

void upd(int p,int k) {
    if(savemode)at[attop++]=svtop;
    for(;p<sizeof t/sizeof*t;p|=p+1)
        if(k>t[p])
        {
            if(savemode)sv[svtop][0]=p,sv[svtop][1]=t[p],++svtop;
            t[p]=k;
        }
}
int qry(int p){ int z=0; for(;p;p&=p-1)z=hi(z,t[p-1]); return z; }
void rollback()
{
    --attop;
    while(svtop>at[attop])
    {
        --svtop;
        int p=sv[svtop][0],k=sv[svtop][1];
        t[p]=k;
    }
}

struct upd { char type; int p, k; } s[1<<22], ss[2][1<<22]; int so;
int bottom=0,sso[2];
void bottomize() { while(bottom<so&&s[bottom].type=='B')++bottom; }

void fix()
{
    if(!so||s[so-1].type=='A')return;
    bottomize();

    for (int j=so-1;(sso[1]!=sso[0]||!sso[0])&&j>=bottom;--j)
        ss[s[j].type=='A'][sso[s[j].type=='A']++]=s[j],rollback();
    so=0;
    for(int j=0;j<2;++j)for(int i=0;i<sso[j];++i)s[so++]=ss[j][i],upd(ss[j][i].p,ss[j][i].k);
    bottomize();
}

void new_phase()
{
    for(int i=so;i--;)rollback();
    for(int i=so;i--;)s[i].type='A',upd(s[i].p,s[i].k);
    bottom=0;
}

void qpop()
{
    bottomize();
    if(bottom==so)new_phase();
    fix();
    --so;
    rollback();
}

void qpush(int p,int k)
{
    s[so].type='B';
    s[so].p=p,s[so].k=k;
    ++so;
    upd(p,k);
}

int c1(int i,int j){return i<j?-1:i>j?1:0;}

int main()
{
    scanf("%d%d",&n,&d);
    for(int i=0;i<n;++i)scanf("%d",a+i),aa[i]=a[i];
    compar=c1;sort(aa,0,n);
    for(int o,i=0;i<n;++i)
    {
        int l=0,r=n-1;
        while(l<=r)o=(l+r)/2,(aa[o]>=a[i])?(r=o-1):(l=o+1);
        a[i]=r+1;
    }
    for(int l=0,i=0;i<n;++i){
        while(i-l>d)qpop(),++l;
        dp[i]=qry(a[i])+1;
        qpush(a[i],dp[i]);
    }
    printf("%d\n",dp[n-1]);
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:99:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     scanf("%d%d",&n,&d);
      |     ^~~~~~~~~~~~~~~~~~~
Main.c:100:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |     for(int i=0;i<n;++i)scanf("%d",a+i),aa[i]=a[i];
      |                         ^~~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35