| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 954585 | sleepntsheep | Advertisement 2 (JOI23_ho_t2) | C11 | 182 ms | 24984 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
