// 5D strict dominance n=1e5: prefix-bitset B=768 + 2D blocking (counting sort) + 5-pass responsibility BF + ordpos(a<d).
#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][100010];
static int first_pos[5][100010];
static int cnt[100010];
static int ordrank[5][5][100010];
static int ordpos[5][5][100010];
static int pos[5][100010];
static u32 partial[100010];
static u32 corr[100010];
static int proc[100010];
static int tmp[100010];
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 = 768;
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 a = 0; a < d; a++)
for (int t = 0; t < n; t++)
ordpos[d][a][t] = pos[a][order[d][t]];
}
size_t prefsz = (size_t)5 * (M + 1) * NWp * sizeof(u64);
const int S = 8192;
{
int p = 0;
for (int s = 0; s < n; s += S) {
int e = s + S; if (e > n) e = n;
int base = p;
for (int t = s; t < e; t++) proc[p++] = order[0][t];
int cntn = e - s;
memset(cnt, 0, sizeof(int) * (n + 1));
for (int i = base; i < base + cntn; i++) cnt[first_pos[1][proc[i]]]++;
int sum = 0;
for (int v = 0; v <= n; v++) { int c = cnt[v]; cnt[v] = sum; sum += c; }
for (int i = base; i < base + cntn; i++) tmp[base + cnt[first_pos[1][proc[i]]]++] = proc[i];
for (int i = base; i < base + cntn; i++) proc[i] = tmp[i];
}
}
void *rawp = malloc(prefsz + 64);
u64 *pref = (u64*)(((size_t)rawp + 63) & ~(size_t)63);
for (int d = 0; d < 5; d++) {
u64 *p = pref + (size_t)d * (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 pt = order[d][t];
cur[pt >> 6] |= 1ULL << (pt & 63);
}
}
}
u64 *p0 = pref;
u64 *p1 = pref + (size_t)(M + 1) * NWp;
u64 *p2 = pref + (size_t)2 * (M + 1) * NWp;
u64 *p3 = pref + (size_t)3 * (M + 1) * NWp;
u64 *p4 = pref + (size_t)4 * (M + 1) * NWp;
// ---- pass 1: AND + popcount (2 points), dims 0-3 normal, dim4 NT ----
for (int pos = 0; pos < n; pos += 2) {
int j0 = proc[pos];
int j1 = (pos + 1 < n) ? proc[pos + 1] : -1;
const u64 *q0a = p0 + (size_t)(first_pos[0][j0] / B) * NWp;
const u64 *q1a = p1 + (size_t)(first_pos[1][j0] / B) * NWp;
const u64 *q2a = p2 + (size_t)(first_pos[2][j0] / B) * NWp;
const u64 *q3a = p3 + (size_t)(first_pos[3][j0] / B) * NWp;
const u64 *q4a = p4 + (size_t)(first_pos[4][j0] / B) * NWp;
const u64 *q0b = q0a, *q1b = q1a, *q2b = q2a, *q3b = q3a, *q4b = q4a;
if (j1 >= 0) {
q0b = p0 + (size_t)(first_pos[0][j1] / B) * NWp;
q1b = p1 + (size_t)(first_pos[1][j1] / B) * NWp;
q2b = p2 + (size_t)(first_pos[2][j1] / B) * NWp;
q3b = p3 + (size_t)(first_pos[3][j1] / B) * NWp;
q4b = p4 + (size_t)(first_pos[4][j1] / B) * NWp;
}
__m256i acc0 = _mm256_setzero_si256();
__m256i acc1 = _mm256_setzero_si256();
int w = 0;
for (; w + 4 <= NW; w += 4) {
__m256i a0 = _mm256_load_si256((const __m256i*)(q0a + w));
__m256i a1 = _mm256_load_si256((const __m256i*)(q1a + w));
__m256i a2 = _mm256_load_si256((const __m256i*)(q2a + w));
__m256i a3 = _mm256_load_si256((const __m256i*)(q3a + w));
__m256i a4 = _mm256_stream_load_si256((__m256i*)(q4a + w));
__m256i b0 = _mm256_load_si256((const __m256i*)(q0b + w));
__m256i b1 = _mm256_load_si256((const __m256i*)(q1b + w));
__m256i b2 = _mm256_load_si256((const __m256i*)(q2b + w));
__m256i b3 = _mm256_load_si256((const __m256i*)(q3b + w));
__m256i b4 = _mm256_stream_load_si256((__m256i*)(q4b + w));
__m256i ra = _mm256_and_si256(_mm256_and_si256(_mm256_and_si256(a0,a1), _mm256_and_si256(a2,a3)), a4);
__m256i rb = _mm256_and_si256(_mm256_and_si256(_mm256_and_si256(b0,b1), _mm256_and_si256(b2,b3)), b4);
acc0 = _mm256_add_epi64(acc0, _mm256_sad_epu8(pc_bytes(ra), _mm256_setzero_si256()));
acc1 = _mm256_add_epi64(acc1, _mm256_sad_epu8(pc_bytes(rb), _mm256_setzero_si256()));
}
u32 c0 = sum4(acc0), c1 = sum4(acc1);
for (; w < NW; w++) {
c0 += (u32)__builtin_popcountll(q0a[w] & q1a[w] & q2a[w] & q3a[w] & q4a[w]);
if (j1 >= 0) c1 += (u32)__builtin_popcountll(q0b[w] & q1b[w] & q2b[w] & q3b[w] & q4b[w]);
}
partial[j0] = c0;
if (j1 >= 0) partial[j1] = c1;
}
// ---- 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 = (1 < 0) ? ((ordrank[0][1][t] / B) * B) : ordrank[0][1][t];
int t1 = (2 < 0) ? ((ordrank[0][2][t] / B) * B) : ordrank[0][2][t];
int t2 = (3 < 0) ? ((ordrank[0][3][t] / B) * B) : ordrank[0][3][t];
int t3 = (4 < 0) ? ((ordrank[0][4][t] / B) * B) : 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 = (0 < 1) ? ((ordrank[1][0][t] / B) * B) : ordrank[1][0][t];
int t1 = (2 < 1) ? ((ordrank[1][2][t] / B) * B) : ordrank[1][2][t];
int t2 = (3 < 1) ? ((ordrank[1][3][t] / B) * B) : ordrank[1][3][t];
int t3 = (4 < 1) ? ((ordrank[1][4][t] / B) * B) : 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 = (0 < 2) ? ((ordrank[2][0][t] / B) * B) : ordrank[2][0][t];
int t1 = (1 < 2) ? ((ordrank[2][1][t] / B) * B) : ordrank[2][1][t];
int t2 = (3 < 2) ? ((ordrank[2][3][t] / B) * B) : ordrank[2][3][t];
int t3 = (4 < 2) ? ((ordrank[2][4][t] / B) * B) : 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 = (0 < 3) ? ((ordrank[3][0][t] / B) * B) : ordrank[3][0][t];
int t1 = (1 < 3) ? ((ordrank[3][1][t] / B) * B) : ordrank[3][1][t];
int t2 = (2 < 3) ? ((ordrank[3][2][t] / B) * B) : ordrank[3][2][t];
int t3 = (4 < 3) ? ((ordrank[3][4][t] / B) * B) : 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 = (0 < 4) ? ((ordrank[4][0][t] / B) * B) : ordrank[4][0][t];
int t1 = (1 < 4) ? ((ordrank[4][1][t] / B) * B) : ordrank[4][1][t];
int t2 = (2 < 4) ? ((ordrank[4][2][t] / B) * B) : ordrank[4][2][t];
int t3 = (3 < 4) ? ((ordrank[4][3][t] / B) * B) : ordrank[4][3][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;
}
}
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 | 169.906 ms | 29 MB + 308 KB | Accepted | Score: 100 | 显示更多 |