// 5D strict dominance n=3e5: prefix-bitset B=64 with dim0-canonical reindex (triangle)
// + 2-point AND over dims 1-4 truncated by the dim0 triangle + 5-pass responsibility BF.
// The prefix is stored over bit-index = pos_0[point] (dim0 position), so pref_0[b] is the
// contiguous triangle [0, b*B): we skip dim0 entirely and read only the first (b0*B)/64 u64s
// of dims 1-4. This halves AND traffic vs reading all 5 full rows.
#pragma GCC target("avx2,bmi")
#pragma GCC optimize("O3")
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <sys/mman.h>
#include <immintrin.h>
typedef unsigned u32;
typedef unsigned long long u64;
static int order[5][300010];
static int first_pos[5][300010];
static int cnt[300010];
static int ordrank[5][5][300010];
static int ordpos[5][5][300010];
static int pos[5][300010];
static u32 partial[300010];
static u32 corr[300010];
static const unsigned char pc_lut_bytes[32] = {
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};
static inline __m256i pc_bytes(__m256i v){
const __m256i lut = _mm256_loadu_si256((const __m256i*)pc_lut_bytes);
const __m256i m4 = _mm256_set1_epi8(0x0F);
__m256i lo = _mm256_and_si256(v, m4);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(v, 4), m4);
lo = _mm256_shuffle_epi8(lut, lo); hi = _mm256_shuffle_epi8(lut, hi);
return _mm256_add_epi8(lo, hi);
}
static inline u32 sum4(__m256i v){
return (u32)(_mm256_extract_epi64(v,0) + _mm256_extract_epi64(v,1)
+ _mm256_extract_epi64(v,2) + _mm256_extract_epi64(v,3));
}
void count_5d(int n, const unsigned *x[5], unsigned *out) {
int NW = (n + 63) >> 6;
int NWp = (NW + 7) & ~7;
const int B = 64;
int M = (n + B - 1) / B;
for (int d = 0; d < 5; d++) {
const unsigned *xd = x[d];
memset(cnt, 0, sizeof(int) * (n + 1));
for (int i = 0; i < n; i++) cnt[xd[i]]++;
int s = 0;
for (int v = 0; v <= (int)n; v++) { int c = cnt[v]; cnt[v] = s; s += c; }
for (int i = 0; i < n; i++) first_pos[d][i] = cnt[xd[i]];
memset(cnt, 0, sizeof(int) * (n + 1));
for (int i = 0; i < n; i++) cnt[xd[i]]++;
for (int v = 1; v <= (int)n; v++) cnt[v] += cnt[v-1];
for (int i = n - 1; i >= 0; i--) order[d][--cnt[xd[i]]] = i;
for (int t = 0; t < n; t++) pos[d][order[d][t]] = t;
}
for (int d = 0; d < 5; d++) {
for (int a = 0; a < 5; a++)
for (int t = 0; t < n; t++)
ordrank[d][a][t] = first_pos[a][order[d][t]];
for (int t = 0; t < n; t++) ordpos[d][0][t] = pos[0][order[d][t]];
for (int a = 1; a < d; a++)
for (int t = 0; t < n; t++)
ordpos[d][a][t] = pos[a][order[d][t]];
}
// Build only dims 1..4, indexed by bit = pos_0 (dim0 position). pref_0 is the free triangle.
size_t prefsz = (size_t)4 * (M + 1) * NWp * sizeof(u64);
void *rawp = malloc(prefsz + 64);
u64 *pref = (u64*)(((size_t)rawp + 63) & ~(size_t)63);
for (int d = 1; d < 5; d++) {
u64 *p = pref + (size_t)(d - 1) * (M + 1) * NWp;
memset(p, 0, (size_t)NWp * sizeof(u64));
for (int b = 0; b < M; b++) {
u64 *cur = p + (size_t)(b + 1) * NWp;
u64 *prev = p + (size_t)b * NWp;
memcpy(cur, prev, (size_t)NWp * sizeof(u64));
int e = (b + 1) * B; if (e > n) e = n;
for (int t = b * B; t < e; t++) {
int r = ordpos[d][0][t];
cur[r >> 6] |= 1ULL << (r & 63);
}
}
}
u64 *p1 = pref;
u64 *p2 = pref + (size_t)(M + 1) * NWp;
u64 *p3 = pref + (size_t)2 * (M + 1) * NWp;
u64 *p4 = pref + (size_t)3 * (M + 1) * NWp;
// ---- pass 1: coarse AND + popcount over dims 1-4, truncated by dim0 triangle (4-point MLP) ----
for (int r = 0; r < n; r += 4) {
int p[4];
int W[4];
const u64 *q[4][4];
int nvalid = n - r; if (nvalid > 4) nvalid = 4;
for (int k = 0; k < 4; k++) {
if (k < nvalid) {
p[k] = order[0][r + k];
W[k] = ((first_pos[0][p[k]] / B) * B) >> 6;
q[k][0] = p1 + (size_t)(first_pos[1][p[k]] / B) * NWp;
q[k][1] = p2 + (size_t)(first_pos[2][p[k]] / B) * NWp;
q[k][2] = p3 + (size_t)(first_pos[3][p[k]] / B) * NWp;
q[k][3] = p4 + (size_t)(first_pos[4][p[k]] / B) * NWp;
} else {
W[k] = 0;
q[k][0] = q[0][0]; q[k][1] = q[0][1]; q[k][2] = q[0][2]; q[k][3] = q[0][3];
}
}
int Wmin = W[0]; if (W[1] < Wmin) Wmin = W[1]; if (W[2] < Wmin) Wmin = W[2]; if (W[3] < Wmin) Wmin = W[3];
__m256i acc0 = _mm256_setzero_si256();
__m256i acc1 = _mm256_setzero_si256();
__m256i acc2 = _mm256_setzero_si256();
__m256i acc3 = _mm256_setzero_si256();
int w = 0;
for (; w + 4 <= Wmin; w += 4) {
{
__m256i a1 = _mm256_load_si256((const __m256i*)(q[0][0] + w));
__m256i a2 = _mm256_load_si256((const __m256i*)(q[0][1] + w));
__m256i a3 = _mm256_load_si256((const __m256i*)(q[0][2] + w));
__m256i a4 = _mm256_load_si256((const __m256i*)(q[0][3] + w));
__m256i rr = _mm256_and_si256(_mm256_and_si256(a1,a2), _mm256_and_si256(a3,a4));
acc0 = _mm256_add_epi64(acc0, _mm256_sad_epu8(pc_bytes(rr), _mm256_setzero_si256()));
}
{
__m256i a1 = _mm256_load_si256((const __m256i*)(q[1][0] + w));
__m256i a2 = _mm256_load_si256((const __m256i*)(q[1][1] + w));
__m256i a3 = _mm256_load_si256((const __m256i*)(q[1][2] + w));
__m256i a4 = _mm256_load_si256((const __m256i*)(q[1][3] + w));
__m256i rr = _mm256_and_si256(_mm256_and_si256(a1,a2), _mm256_and_si256(a3,a4));
acc1 = _mm256_add_epi64(acc1, _mm256_sad_epu8(pc_bytes(rr), _mm256_setzero_si256()));
}
{
__m256i a1 = _mm256_load_si256((const __m256i*)(q[2][0] + w));
__m256i a2 = _mm256_load_si256((const __m256i*)(q[2][1] + w));
__m256i a3 = _mm256_load_si256((const __m256i*)(q[2][2] + w));
__m256i a4 = _mm256_load_si256((const __m256i*)(q[2][3] + w));
__m256i rr = _mm256_and_si256(_mm256_and_si256(a1,a2), _mm256_and_si256(a3,a4));
acc2 = _mm256_add_epi64(acc2, _mm256_sad_epu8(pc_bytes(rr), _mm256_setzero_si256()));
}
{
__m256i a1 = _mm256_load_si256((const __m256i*)(q[3][0] + w));
__m256i a2 = _mm256_load_si256((const __m256i*)(q[3][1] + w));
__m256i a3 = _mm256_load_si256((const __m256i*)(q[3][2] + w));
__m256i a4 = _mm256_load_si256((const __m256i*)(q[3][3] + w));
__m256i rr = _mm256_and_si256(_mm256_and_si256(a1,a2), _mm256_and_si256(a3,a4));
acc3 = _mm256_add_epi64(acc3, _mm256_sad_epu8(pc_bytes(rr), _mm256_setzero_si256()));
}
}
u32 c[4];
c[0] = sum4(acc0); c[1] = sum4(acc1); c[2] = sum4(acc2); c[3] = sum4(acc3);
for (int k = 0; k < nvalid; k++) {
for (int ww = w; ww < W[k]; ww++)
c[k] += (u32)__builtin_popcountll(q[k][0][ww] & q[k][1][ww] & q[k][2][ww] & q[k][3][ww]);
partial[p[k]] = c[k];
}
}
// ---- pass 2: 5-pass responsibility brute force (exact, zero dedup) ----
memset(corr, 0, sizeof(u32) * n);
{
int* A0 = ordrank[0][1];
int* A1 = ordrank[0][2];
int* A2 = ordrank[0][3];
int* A3 = ordrank[0][4];
int* Dsel = ordrank[0][0];
int* Ord = order[0];
for (int t = 0; t < n; t++) {
int j = Ord[t];
int f = Dsel[t];
int bs = (f / B) * B;
int t0 = ordrank[0][1][t];
int t1 = ordrank[0][2][t];
int t2 = ordrank[0][3][t];
int t3 = ordrank[0][4][t];
__m256i v0 = _mm256_set1_epi32(t0);
__m256i v1 = _mm256_set1_epi32(t1);
__m256i v2 = _mm256_set1_epi32(t2);
__m256i v3 = _mm256_set1_epi32(t3);
int p = bs;
int cntm = 0;
for (; p + 16 <= f; p += 16) {
__m256i a0 = _mm256_loadu_si256((const __m256i*)(A0 + p));
__m256i a0b = _mm256_loadu_si256((const __m256i*)(A0 + p + 8));
__m256i a1 = _mm256_loadu_si256((const __m256i*)(A1 + p));
__m256i a1b = _mm256_loadu_si256((const __m256i*)(A1 + p + 8));
__m256i a2 = _mm256_loadu_si256((const __m256i*)(A2 + p));
__m256i a2b = _mm256_loadu_si256((const __m256i*)(A2 + p + 8));
__m256i a3 = _mm256_loadu_si256((const __m256i*)(A3 + p));
__m256i a3b = _mm256_loadu_si256((const __m256i*)(A3 + p + 8));
__m256i ma = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0), _mm256_cmpgt_epi32(v1,a1)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2), _mm256_cmpgt_epi32(v3,a3)));
__m256i mb = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0b), _mm256_cmpgt_epi32(v1,a1b)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2b), _mm256_cmpgt_epi32(v3,a3b)));
int mask = _mm256_movemask_ps(_mm256_castsi256_ps(ma)) | (_mm256_movemask_ps(_mm256_castsi256_ps(mb)) << 8);
cntm += __builtin_popcount(mask);
}
for (; p < f; p++) {
if (A0[p] < t0 && A1[p] < t1 && A2[p] < t2 && A3[p] < t3) cntm++;
}
corr[j] += cntm;
}
}
{
int* A0 = ordpos[1][0];
int* A1 = ordrank[1][2];
int* A2 = ordrank[1][3];
int* A3 = ordrank[1][4];
int* Dsel = ordrank[1][1];
int* Ord = order[1];
for (int t = 0; t < n; t++) {
int j = Ord[t];
int f = Dsel[t];
int bs = (f / B) * B;
int t0 = (ordrank[1][0][t] / B) * B;
int t1 = ordrank[1][2][t];
int t2 = ordrank[1][3][t];
int t3 = ordrank[1][4][t];
__m256i v0 = _mm256_set1_epi32(t0);
__m256i v1 = _mm256_set1_epi32(t1);
__m256i v2 = _mm256_set1_epi32(t2);
__m256i v3 = _mm256_set1_epi32(t3);
int p = bs;
int cntm = 0;
for (; p + 16 <= f; p += 16) {
__m256i a0 = _mm256_loadu_si256((const __m256i*)(A0 + p));
__m256i a0b = _mm256_loadu_si256((const __m256i*)(A0 + p + 8));
__m256i a1 = _mm256_loadu_si256((const __m256i*)(A1 + p));
__m256i a1b = _mm256_loadu_si256((const __m256i*)(A1 + p + 8));
__m256i a2 = _mm256_loadu_si256((const __m256i*)(A2 + p));
__m256i a2b = _mm256_loadu_si256((const __m256i*)(A2 + p + 8));
__m256i a3 = _mm256_loadu_si256((const __m256i*)(A3 + p));
__m256i a3b = _mm256_loadu_si256((const __m256i*)(A3 + p + 8));
__m256i ma = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0), _mm256_cmpgt_epi32(v1,a1)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2), _mm256_cmpgt_epi32(v3,a3)));
__m256i mb = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0b), _mm256_cmpgt_epi32(v1,a1b)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2b), _mm256_cmpgt_epi32(v3,a3b)));
int mask = _mm256_movemask_ps(_mm256_castsi256_ps(ma)) | (_mm256_movemask_ps(_mm256_castsi256_ps(mb)) << 8);
cntm += __builtin_popcount(mask);
}
for (; p < f; p++) {
if (A0[p] < t0 && A1[p] < t1 && A2[p] < t2 && A3[p] < t3) cntm++;
}
corr[j] += cntm;
}
}
{
int* A0 = ordpos[2][0];
int* A1 = ordpos[2][1];
int* A2 = ordrank[2][3];
int* A3 = ordrank[2][4];
int* Dsel = ordrank[2][2];
int* Ord = order[2];
for (int t = 0; t < n; t++) {
int j = Ord[t];
int f = Dsel[t];
int bs = (f / B) * B;
int t0 = (ordrank[2][0][t] / B) * B;
int t1 = (ordrank[2][1][t] / B) * B;
int t2 = ordrank[2][3][t];
int t3 = ordrank[2][4][t];
__m256i v0 = _mm256_set1_epi32(t0);
__m256i v1 = _mm256_set1_epi32(t1);
__m256i v2 = _mm256_set1_epi32(t2);
__m256i v3 = _mm256_set1_epi32(t3);
int p = bs;
int cntm = 0;
for (; p + 16 <= f; p += 16) {
__m256i a0 = _mm256_loadu_si256((const __m256i*)(A0 + p));
__m256i a0b = _mm256_loadu_si256((const __m256i*)(A0 + p + 8));
__m256i a1 = _mm256_loadu_si256((const __m256i*)(A1 + p));
__m256i a1b = _mm256_loadu_si256((const __m256i*)(A1 + p + 8));
__m256i a2 = _mm256_loadu_si256((const __m256i*)(A2 + p));
__m256i a2b = _mm256_loadu_si256((const __m256i*)(A2 + p + 8));
__m256i a3 = _mm256_loadu_si256((const __m256i*)(A3 + p));
__m256i a3b = _mm256_loadu_si256((const __m256i*)(A3 + p + 8));
__m256i ma = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0), _mm256_cmpgt_epi32(v1,a1)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2), _mm256_cmpgt_epi32(v3,a3)));
__m256i mb = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0b), _mm256_cmpgt_epi32(v1,a1b)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2b), _mm256_cmpgt_epi32(v3,a3b)));
int mask = _mm256_movemask_ps(_mm256_castsi256_ps(ma)) | (_mm256_movemask_ps(_mm256_castsi256_ps(mb)) << 8);
cntm += __builtin_popcount(mask);
}
for (; p < f; p++) {
if (A0[p] < t0 && A1[p] < t1 && A2[p] < t2 && A3[p] < t3) cntm++;
}
corr[j] += cntm;
}
}
{
int* A0 = ordpos[3][0];
int* A1 = ordpos[3][1];
int* A2 = ordpos[3][2];
int* A3 = ordrank[3][4];
int* Dsel = ordrank[3][3];
int* Ord = order[3];
for (int t = 0; t < n; t++) {
int j = Ord[t];
int f = Dsel[t];
int bs = (f / B) * B;
int t0 = (ordrank[3][0][t] / B) * B;
int t1 = (ordrank[3][1][t] / B) * B;
int t2 = (ordrank[3][2][t] / B) * B;
int t3 = ordrank[3][4][t];
__m256i v0 = _mm256_set1_epi32(t0);
__m256i v1 = _mm256_set1_epi32(t1);
__m256i v2 = _mm256_set1_epi32(t2);
__m256i v3 = _mm256_set1_epi32(t3);
int p = bs;
int cntm = 0;
for (; p + 16 <= f; p += 16) {
__m256i a0 = _mm256_loadu_si256((const __m256i*)(A0 + p));
__m256i a0b = _mm256_loadu_si256((const __m256i*)(A0 + p + 8));
__m256i a1 = _mm256_loadu_si256((const __m256i*)(A1 + p));
__m256i a1b = _mm256_loadu_si256((const __m256i*)(A1 + p + 8));
__m256i a2 = _mm256_loadu_si256((const __m256i*)(A2 + p));
__m256i a2b = _mm256_loadu_si256((const __m256i*)(A2 + p + 8));
__m256i a3 = _mm256_loadu_si256((const __m256i*)(A3 + p));
__m256i a3b = _mm256_loadu_si256((const __m256i*)(A3 + p + 8));
__m256i ma = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0), _mm256_cmpgt_epi32(v1,a1)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2), _mm256_cmpgt_epi32(v3,a3)));
__m256i mb = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0b), _mm256_cmpgt_epi32(v1,a1b)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2b), _mm256_cmpgt_epi32(v3,a3b)));
int mask = _mm256_movemask_ps(_mm256_castsi256_ps(ma)) | (_mm256_movemask_ps(_mm256_castsi256_ps(mb)) << 8);
cntm += __builtin_popcount(mask);
}
for (; p < f; p++) {
if (A0[p] < t0 && A1[p] < t1 && A2[p] < t2 && A3[p] < t3) cntm++;
}
corr[j] += cntm;
}
}
{
int* A0 = ordpos[4][0];
int* A1 = ordpos[4][1];
int* A2 = ordpos[4][2];
int* A3 = ordpos[4][3];
int* Dsel = ordrank[4][4];
int* Ord = order[4];
for (int t = 0; t < n; t++) {
int j = Ord[t];
int f = Dsel[t];
int bs = (f / B) * B;
int t0 = (ordrank[4][0][t] / B) * B;
int t1 = (ordrank[4][1][t] / B) * B;
int t2 = (ordrank[4][2][t] / B) * B;
int t3 = (ordrank[4][3][t] / B) * B;
__m256i v0 = _mm256_set1_epi32(t0);
__m256i v1 = _mm256_set1_epi32(t1);
__m256i v2 = _mm256_set1_epi32(t2);
__m256i v3 = _mm256_set1_epi32(t3);
int p = bs;
int cntm = 0;
for (; p + 16 <= f; p += 16) {
__m256i a0 = _mm256_loadu_si256((const __m256i*)(A0 + p));
__m256i a0b = _mm256_loadu_si256((const __m256i*)(A0 + p + 8));
__m256i a1 = _mm256_loadu_si256((const __m256i*)(A1 + p));
__m256i a1b = _mm256_loadu_si256((const __m256i*)(A1 + p + 8));
__m256i a2 = _mm256_loadu_si256((const __m256i*)(A2 + p));
__m256i a2b = _mm256_loadu_si256((const __m256i*)(A2 + p + 8));
__m256i a3 = _mm256_loadu_si256((const __m256i*)(A3 + p));
__m256i a3b = _mm256_loadu_si256((const __m256i*)(A3 + p + 8));
__m256i ma = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0), _mm256_cmpgt_epi32(v1,a1)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2), _mm256_cmpgt_epi32(v3,a3)));
__m256i mb = _mm256_and_si256(_mm256_and_si256(_mm256_cmpgt_epi32(v0,a0b), _mm256_cmpgt_epi32(v1,a1b)), _mm256_and_si256(_mm256_cmpgt_epi32(v2,a2b), _mm256_cmpgt_epi32(v3,a3b)));
int mask = _mm256_movemask_ps(_mm256_castsi256_ps(ma)) | (_mm256_movemask_ps(_mm256_castsi256_ps(mb)) << 8);
cntm += __builtin_popcount(mask);
}
for (; p < f; p++) {
if (A0[p] < t0 && A1[p] < t1 && A2[p] < t2 && A3[p] < t3) cntm++;
}
corr[j] += cntm;
}
}
for (int i = 0; i < n; i++) out[i] = partial[i] + corr[i];
free(rawp);
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 1.404 s | 733 MB + 832 KB | Accepted | Score: 100 | 显示更多 |