Submission #954585

#	Time	Username	Problem	Language	Result	Execution time	Memory
954585		sleepntsheep	Advertisement 2 (JOI23_ho_t2)	C11	100 / 100	182 ms	24984 KiB

Main

unsigned rng=12345;
int rand_(){return (rng*=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;
    }
}

#include<stdio.h>
#define N 500001
int n,a[N],b[N],o[N],x[N],y[N],z[N];

int compar_a(int i,int j) { return a[i]<a[j]?-1:a[i]>a[j]?1:0; }

int s[N],so,t[N],to;

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d%d",a+i,b+i),o[i]=i;
    compar=compar_a;
    sort_(o,0,n);

    for(int i=0;i<n;++i)x[i]=a[o[i]],y[i]=a[o[i]]+b[o[i]],z[i]=b[o[i]]-a[o[i]];

    for(int i=0;i<n;++i)
    {
        while(so&&z[s[so-1]]<=z[i])--so;
        s[so++]=i;
    }


    for(int j=so-1;j>=0;--j)
    {
        while(to&&y[t[to-1]]<=y[s[j]])--to;
        t[to++]=s[j];
    }
    printf("%d",to);

}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 23 / 23
• Subtask 3: 36 / 36
• Subtask 4: 31 / 31