代码

#include <pthread.h>
#include <string.h>
typedef unsigned u32;
enum{N=10000005,L=4096,H=2442,T=4,HP=2448};
typedef struct{u32 x,y,id,z;}P;
typedef struct{u32 v[HP];}Row;
static P a[N],b[N];static Row cnt[T],pos[T],add[T];static u32 yb[H+1],xb[H+1];
static const u32*xx,*yy;static u32*oo;static int nn;static pthread_barrier_t bar;

static __attribute__((noinline))void low(P*s,int l,int r){
 u32 f[L+1]={0};
 for(int i=l;i<r;++i){P*q=s+i;u32 x=q->x&4095,z=0;for(u32 k=x;k;k&=k-1)z+=f[k];q->z+=z;for(u32 k=x+1;k<=L;k+=k&-k)++f[k];oo[q->id]=q->z;}
}
static void*run(void*arg){int id=(int)(long)arg,n=nn,l=(int)((long long)n*id/T),r=(int)((long long)n*(id+1)/T);
 memset(cnt[id].v,0,H*sizeof(u32));for(int i=l;i<r;++i)++cnt[id].v[yy[i]>>12];pthread_barrier_wait(&bar);
 if(!id){u32 z=0;yb[0]=0;for(int q=0;q<H;++q){yb[q]=z;for(int t=0;t<T;++t){pos[t].v[q]=z;z+=cnt[t].v[q];}}yb[H]=z;}pthread_barrier_wait(&bar);
 for(int i=l;i<r;++i){u32 y=yy[i],q=y>>12;a[pos[id].v[q]++]=(P){xx[i],y,(u32)i,0};}pthread_barrier_wait(&bar);
 for(int h=id;h<H;h+=T){int ll=yb[h],rr=yb[h+1];if(ll==rr)continue;u32 c[L]={0},p[L];for(int i=ll;i<rr;++i)++c[a[i].y&4095];u32 z=ll;for(int q=0;q<L;++q){u32 w=c[q];p[q]=z;z+=w;}for(int i=ll;i<rr;++i){P w=a[i];b[p[w.y&4095]++]=w;}}
 pthread_barrier_wait(&bar);
 for(int h=id;h<H;h+=T){int ll=yb[h],rr=yb[h+1];for(int f=ll;f<rr;){int e=f+1;while(e<rr&&b[e].y==b[f].y)++e;for(int i=f+1;i<e;++i){P w=b[i];int j=i;while(j>f&&b[j-1].x>w.x)b[j]=b[j-1],--j;b[j]=w;}for(int q=f;q<e;){int t=q+1;while(t<e&&b[t].x==b[q].x)++t;u32 w=q-f;for(int i=q;i<t;++i)b[i].z=0-w;q=t;}f=e;}}
 pthread_barrier_wait(&bar);
 memset(cnt[id].v,0,H*sizeof(u32));u32 fw[H+1]={0};
 for(int i=l;i<r;++i){P*q=b+i;u32 x=q->x>>12,z=0;for(u32 k=x;k;k&=k-1)z+=fw[k];q->z+=z;++cnt[id].v[x];for(u32 k=x+1;k<=H;k+=k&-k)++fw[k];}
 pthread_barrier_wait(&bar);
 if(!id){u32 prev[H]={0};for(int t=0;t<T;++t){u32 z=0;for(int q=0;q<H;++q){add[t].v[q]=z;z+=prev[q];}for(int q=0;q<H;++q)prev[q]+=cnt[t].v[q];}u32 z=0;xb[0]=0;for(int q=0;q<H;++q){xb[q]=z;for(int t=0;t<T;++t){pos[t].v[q]=z;z+=cnt[t].v[q];}}xb[H]=z;}
 pthread_barrier_wait(&bar);
 for(int i=l;i<r;++i){P w=b[i];u32 q=w.x>>12;w.z+=add[id].v[q];a[pos[id].v[q]++]=w;}
 pthread_barrier_wait(&bar);
 for(int h=id;h<H;h+=T)if(xb[h]<xb[h+1])low(a,xb[h],xb[h+1]);
 return 0;
}
void count_2d(int n,const u32*x,const u32*y,u32*out){pthread_t th[T-1];nn=n;xx=x;yy=y;oo=out;pthread_barrier_init(&bar,0,T);for(long t=1;t<T;++t)pthread_create(th+t-1,0,run,(void*)t);run(0);for(int t=1;t<T;++t)pthread_join(th[t-1],0);pthread_barrier_destroy(&bar);}

评测结果