代码

#include <immintrin.h>
typedef unsigned u32;typedef unsigned long u64;typedef unsigned long U;
#ifndef CAPACITY
#define CAPACITY 100005
#endif
#ifndef BLOCK_SIZE
#define BLOCK_SIZE 96
#endif
enum{N=CAPACITY,B=BLOCK_SIZE,W=(N+63)/64,NB=(N+B-1)/B+1};
static int sd[5][N],cnt[N],st[N],rp[5][N],lo[5][N];static unsigned char owner[N];
static u64 active[W],cur[W],pre[15][NB][W];
__attribute__((target("avx2"),always_inline))static inline void csa(__m256i*h,__m256i*l,__m256i a,__m256i b,__m256i c){__m256i u=_mm256_xor_si256(a,b);*h=_mm256_or_si256(_mm256_and_si256(a,b),_mm256_and_si256(u,c));*l=_mm256_xor_si256(u,c);}
__attribute__((target("avx2"),always_inline))static inline __m256i vpc(__m256i v,__m256i lut,__m256i mask,__m256i zero){__m256i lo=_mm256_and_si256(v,mask),hi=_mm256_and_si256(_mm256_srli_epi16(v,4),mask);return _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lut,lo),_mm256_shuffle_epi8(lut,hi)),zero);}
__attribute__((target("avx2,popcnt"),always_inline))static inline u32 pc(int words,const u64*a,const u64*b,const u64*c,const u64*d){const __m256i lut=_mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4),mask=_mm256_set1_epi8(15),zero=_mm256_setzero_si256();__m256i ones=zero,twos=zero,fours=zero,total=zero,ta,tb,fa,fb,e;int i=0;
#define V(j) _mm256_and_si256(_mm256_loadu_si256((const __m256i*)(a+i+4*(j))),_mm256_and_si256(_mm256_loadu_si256((const __m256i*)(b+i+4*(j))),_mm256_and_si256(_mm256_loadu_si256((const __m256i*)(c+i+4*(j))),_mm256_loadu_si256((const __m256i*)(d+i+4*(j))))))
 for(;i+32<=words;i+=32){csa(&ta,&ones,ones,V(0),V(1));csa(&tb,&ones,ones,V(2),V(3));csa(&fa,&twos,twos,ta,tb);csa(&ta,&ones,ones,V(4),V(5));csa(&tb,&ones,ones,V(6),V(7));csa(&fb,&twos,twos,ta,tb);csa(&e,&fours,fours,fa,fb);total=_mm256_add_epi64(total,vpc(e,lut,mask,zero));}
#undef V
 total=_mm256_slli_epi64(total,3);total=_mm256_add_epi64(total,_mm256_slli_epi64(vpc(fours,lut,mask,zero),2));total=_mm256_add_epi64(total,_mm256_slli_epi64(vpc(twos,lut,mask,zero),1));total=_mm256_add_epi64(total,vpc(ones,lut,mask,zero));u64 q[4]__attribute__((aligned(32)));_mm256_store_si256((__m256i*)q,total);u64 z=q[0]+q[1]+q[2]+q[3];for(;i<words;++i)z+=__builtin_popcountll(a[i]&b[i]&c[i]&d[i]);return(u32)z;}
static void sortdim(int d,int n,const u32*x){__builtin_memset(cnt,0,(unsigned)n*4);for(int i=0;i<n;++i)++cnt[x[i]];int z=0;for(int q=0;q<n;++q){int t=cnt[q];st[q]=z;cnt[q]=z;z+=t;}for(int i=0;i<n;++i){int p=cnt[x[i]]++;sd[d][p]=i;rp[d][i]=p;lo[d][i]=st[x[i]];}}
static void build(int ix,int d,int a,int n,int words){__builtin_memset(cur,0,(unsigned)words*8);int blocks=(n+B-1)/B;for(int b=1;b<=blocks;++b){int e=b*B;if(e>n)e=n;for(int p=(b-1)*B;p<e;++p){int id=sd[d][p],q=rp[a][id];cur[q>>6]|=1ul<<(q&63);}__builtin_memcpy(pre[ix][b],cur,(unsigned)words*8);}}
__attribute__((target("avx2,popcnt")))void count_5d(int n,const u32*x[5],u32*out){int words=(n+63)>>6;for(int d=0;d<5;++d)sortdim(d,n,x[d]);for(int a=0;a<5;++a)for(int k=0;k<3;++k)build(3*a+k,(a+2+k)%5,a,n,words);for(int i=0;i<n;++i){int a=0;for(int d=1;d<5;++d)if(lo[d][i]<lo[a][i])a=d;owner[i]=a;}
 for(int a=0;a<5;++a){__builtin_memset(active,0,(unsigned)words*8);int s=(a+1)%5,d0=(a+2)%5,d1=(a+3)%5,d2=(a+4)%5;for(int f=0;f<n;){int e=f+1;u32 sv=x[s][sd[s][f]];while(e<n&&x[s][sd[s][e]]==sv)++e;for(int qi=f;qi<e;++qi){int id=sd[s][qi];if(owner[id]!=a)continue;int lim=lo[a][id],l0=lo[d0][id],l1=lo[d1][id],l2=lo[d2][id],b0=(l0+B-1)/B,b1=(l1+B-1)/B,b2=(l2+B-1)/B,e0=b0*B,e1=b1*B,e2=b2*B;if(e0>n)e0=n;if(e1>n)e1=n;if(e2>n)e2=n;u64*p0=pre[3*a][b0],*p1=pre[3*a+1][b1],*p2=pre[3*a+2][b2];u32 res=pc(lim>>6,active,p0,p1,p2);int rem=lim&63;if(rem)res+=__builtin_popcountll(active[lim>>6]&p0[lim>>6]&p1[lim>>6]&p2[lim>>6]&((1ul<<rem)-1));for(int p=l0;p<e0;++p){int q=sd[d0][p],bit=rp[a][q];if(bit<lim&&((active[bit>>6]>>(bit&63))&1)&&rp[d1][q]<e1&&rp[d2][q]<e2)--res;}for(int p=l1;p<e1;++p){int q=sd[d1][p],bit=rp[a][q];if(bit<lim&&((active[bit>>6]>>(bit&63))&1)&&rp[d0][q]<l0&&rp[d2][q]<e2)--res;}for(int p=l2;p<e2;++p){int q=sd[d2][p],bit=rp[a][q];if(bit<lim&&((active[bit>>6]>>(bit&63))&1)&&rp[d0][q]<l0&&rp[d1][q]<l1)--res;}out[id]=res;}for(int p=f;p<e;++p){int q=rp[a][sd[s][p]];active[q>>6]|=1ul<<(q&63);}f=e;}}}
#ifndef LOCAL
static char**v;static U ac_;U getauxval(U k){char**p=v+ac_+1;while(*p)++p;U*q=(U*)(p+1);while(*q){if(*q==k)return q[1];q+=2;}return 0;}__attribute__((noreturn))void __libc_start_main(int(*e)(int,char**,char**),int ac,char**av){ac_=ac;v=av;e(ac,av,0);__asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall":::"rax","rdi","rcx","r11","memory");__builtin_unreachable();}
#endif

评测结果