#pragma GCC optimize("no-branch-count-reg","unroll-all-loops","align-functions=32","align-jumps=64","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=haswell")
// 1009 "3D dominance counting" (n = 1e6), FUNCTION-style.
// STATUS: the AC submission on duck.ac (sid 86372, 552.337 ms, rank #1; previous
// #1 was 745.15 ms) used exactly this code (sol_best.cpp == that submission).
// Algorithm: counting-sort by x, CDQ over x-order (midpoint splits; y-merge fused
// with the cross-counting), branchless hierarchical z-prefix counter.
// A faster (~25%) variant lives in sol_candidate_v3.cpp: group-boundary splits,
// 16-byte AoS records (no XS/XPM arrays). It passed 14400 randomised stress runs
// vs brute force and 8 large-n runs vs an independent CDQ reference, but is not
// submitted yet: duck.ac submissions were paused (data/PAUSE) at the time.
// 1009 - 3D dominance counting (n = 1e6).
// CDQ over x (merge by y, fused counting) + hierarchical z-counter (branchless).
//
// record (16 bytes, array-of-structs):
// w0 = (y << 40) | (orig << 20) | A A accumulates the answer
// w1 = (T << 40) | (R << 20) | x T = #{z' < z} (query bound)
// R = unique rank in z order (insert key)
// All fields < 2^20 (n <= 1e6).
#include <string.h>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
typedef unsigned u32;
typedef unsigned long long u64;
typedef unsigned char u8;
typedef unsigned short u16;
static const int MAXN = 1000001;
#define W_Y(v) ((u32)((v) >> 40))
#define W_ORIG(v) ((u32)(((v) >> 20) & 0xFFFFFu))
#define W_A(v) ((u32)((v) & 0xFFFFFu))
#define W_T(v) ((u32)((v) >> 40))
#define W_R(v) ((u32)(((v) >> 20) & 0xFFFFFu))
#define W_X(v) ((u32)((v) & 0xFFFFFu))
// +16 u64 of pad per row keeps the two buffers off a 4096-byte multiple (4K aliasing)
static u64 RC[2][2 * (MAXN + 8)] __attribute__((aligned(64)));
static u64 P1[MAXN]; // pre-record w1 only; w0 is built at the scatter
static u64 TIE[(MAXN + 63) / 64 + 8]; // TIE[p] bit = (x[p-1] == x[p])
// H32 and CNT are live ONLY during the BUILD. H32 packs (groupStart<<12)|tieIndex so the
// whole z-compression table is 4 MB -- L3-resident, where the 8-byte form was not.
#define H32 ((u32 *)(void *)RC[1])
#define CNT ((u32 *)(void *)((u64 *)RC[1] + (MAXN + 8) / 2))
// ---------- hybrid counter: cumulative above 2^10, block counts below ----------
// C2[j], j=T>>10 : # ranks in [(j>>4)<<14, j<<10) within a 2^14 group, 16 x u16
// C3[j], j=T>>14 : # ranks in [(j>>4)<<18, j<<14) within a 2^18 group, 16 x u32
// C4[j], j=T>>18 : # ranks in [0, j<<18) global, <= 4 x u32 at n<=1e6
// ---- ARM PACK: every counter array and both mask tables live in ONE object, so the
// ---- fused loop needs ONE base pointer instead of five. Layout/contents unchanged.
struct alignas(64) CTRT {
alignas(32) u64 ZB[(MAXN + 63) / 64 + 16];
alignas(32) u8 ZW1[(MAXN + 63) / 64 + 32];
alignas(32) u8 ZWM[16][16];
alignas(32) u16 C2[(MAXN >> 10) + 64];
alignas(32) u32 C3[(MAXN >> 14) + 32];
alignas(32) u32 C4[(MAXN >> 17) + 32];
alignas(32) u16 MSKB[16][16];
alignas(32) u32 MSKC[16][16];
alignas(16) u32 MSKD[4][4];
alignas(32) u32 MSKE[8][8];
u8 MSKW[16][16];
};
static CTRT CT;
#define ZB (CT.ZB)
#define ZW1 (CT.ZW1)
#define C2 (CT.C2)
#define C3 (CT.C3)
#define C4 (CT.C4)
#define MSKB (CT.MSKB)
#define MSKC (CT.MSKC)
#define MSKD (CT.MSKD)
#define MSKE (CT.MSKE)
#define MSKW (CT.MSKW)
static int g_msk_init = 0;
static inline void msk_init(void) {
if (g_msk_init) return;
for (int p = 0; p < 16; p++)
for (int i = 0; i < 16; i++) { MSKB[p][i] = (u16)(i > p); MSKC[p][i] = (u32)(i > p); }
for (int p = 0; p < 4; p++)
for (int i = 0; i < 4; i++) MSKD[p][i] = (u32)(i > p);
for (int p = 0; p < 8; p++)
for (int i = 0; i < 8; i++) MSKE[p][i] = (u32)(i > p);
for (int p = 0; p < 16; p++)
for (int i = 0; i < 16; i++) MSKW[p][i] = (u8)(i < p ? 0xFF : 0x00);
g_msk_init = 1;
}
static inline void sadd16(u16 *arr, u32 idx) {
__m256i m = _mm256_load_si256((const __m256i *)MSKB[idx & 15]);
__m256i *a = (__m256i *)(void *)(arr + (idx & ~15u));
_mm256_store_si256(a, _mm256_add_epi16(_mm256_load_si256(a), m));
}
static inline void ssub16(u16 *arr, u32 idx) {
__m256i m = _mm256_load_si256((const __m256i *)MSKB[idx & 15]);
__m256i *a = (__m256i *)(void *)(arr + (idx & ~15u));
_mm256_store_si256(a, _mm256_sub_epi16(_mm256_load_si256(a), m));
}
static inline void sadd8(u32 *arr, u32 idx) {
const __m256i *m = (const __m256i *)MSKE[idx & 7];
__m256i *a = (__m256i *)(void *)(arr + (idx & ~7u));
_mm256_store_si256(a, _mm256_add_epi32(_mm256_load_si256(a), _mm256_load_si256(m)));
}
static inline void ssub8(u32 *arr, u32 idx) {
const __m256i *m = (const __m256i *)MSKE[idx & 7];
__m256i *a = (__m256i *)(void *)(arr + (idx & ~7u));
_mm256_store_si256(a, _mm256_sub_epi32(_mm256_load_si256(a), _mm256_load_si256(m)));
}
template <int LV> static inline void zadd(u32 r) {
ZB[r >> 6] |= 1ull << (r & 63);
ZW1[r >> 6]++;
sadd16(C2, r >> 10);
sadd8(C3, r >> 14);
sadd8(C4, r >> 17);
}
template <int LV> static inline void zsub(u32 r) {
ZB[r >> 6] &= ~(1ull << (r & 63));
ZW1[r >> 6]--;
ssub16(C2, r >> 10);
ssub8(C3, r >> 14);
ssub8(C4, r >> 17);
}
static inline __m256i mkI16() { return _mm256_setr_epi16(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); }
static inline __m128i mkI8() { return _mm_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); }
static inline __m256i mkOne16() { return _mm256_set1_epi16(1); }
template <int LV> static inline u32 zquery(u32 T) {
u32 k1 = (T >> 6) & 15;
__m128i bz = _mm_and_si128(_mm_loadu_si128((const __m128i *)(ZW1 + ((T >> 10) << 4))),
_mm_loadu_si128((const __m128i *)(MSKW[k1])));
__m128i sd = _mm_sad_epu8(bz, _mm_setzero_si128());
return (u32)C4[T >> 17] + (u32)C3[T >> 14] + (u32)C2[T >> 10]
+ (u32)_mm_cvtsi128_si32(_mm_add_epi64(sd, _mm_srli_si128(sd, 8)))
+ (u32)__builtin_popcountll(_bzhi_u64(ZB[T >> 6], T & 63));
}
#ifndef SIMD_LIM
#define SIMD_LIM 128
#endif
// count records in [l,i) whose R < T (4 records per AVX iteration)
static inline u32 count_lt(const u64 *S, int l, int i, u32 T) {
u32 c = 0;
int k = l;
const __m256i m20 = _mm256_set1_epi64x(0xFFFFF);
for (; k + 2 <= i; k += 2) { // two records = 4 u64 lanes
__m256i v = _mm256_loadu_si256((const __m256i *)(S + 2 * k)); // {w0,w1,w0,w1}
__m256i r = _mm256_and_si256(_mm256_srli_epi64(v, 20), m20);
__m256i cm = _mm256_cmpgt_epi64(_mm256_set1_epi64x((long long)T), r);
c += (u32)__builtin_popcount((u32)_mm256_movemask_pd(_mm256_castsi256_pd(cm)) & 0xAu);
}
for (; k < i; k++) if (W_R(S[2 * k + 1]) < T) c++;
return c;
}
// fused y-merge + cross count (no x-ties: every left x < every right x)
template <int LV> static void node_fused(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
int a = l, b = m;
u64 *Dt = D + 2 * l;
u64 *Sa = S + 2 * l, *Sb = S + 2 * m;
while (a < m && b < r) {
u64 w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if ((w0b >> 40) <= (w0a >> 40)) { // right first on equal y (strict)
w0b += zquery<LV>((u32)(w1b >> 40));
Dt[0] = w0b; Dt[1] = w1b; Sb += 2; b++;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
Dt[0] = w0a; Dt[1] = w1a; Sa += 2; a++;
}
Dt += 2;
}
int aIns = a;
while (b < r) {
u32 c = zquery<LV>(W_T(Sb[1]));
Sb[0] += c;
Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb += 2; b++; Dt += 2;
}
while (a < m) { Dt[0] = Sa[0]; Dt[1] = Sa[1]; Sa += 2; a++; Dt += 2; }
for (int k = l; k < aIns; k++) zsub<LV>(W_R(S[k * 2 + 1]));
}
// ---- FULL fuse: same sweep as node_fused, but NO undo and the R half is inserted at the
// ---- end, so the counter is left holding exactly [l,r).
template <int LV> static void node_fused_full(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
int a = l, b = m;
u64 *Dt = D + 2 * l;
u64 *Sa = S + 2 * l, *Sb = S + 2 * m;
while (a < m && b < r) {
u64 w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if ((w0b >> 40) <= (w0a >> 40)) {
w0b += zquery<LV>((u32)(w1b >> 40));
Dt[0] = w0b; Dt[1] = w1b; Sb += 2; b++;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
Dt[0] = w0a; Dt[1] = w1a; Sa += 2; a++;
}
Dt += 2;
}
while (b < r) {
u32 c = zquery<LV>(W_T(Sb[1]));
Sb[0] += c;
Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb += 2; b++; Dt += 2;
}
while (a < m) { // remaining LEFT elements go in as well
zadd<LV>(W_R(Sa[1]));
Dt[0] = Sa[0]; Dt[1] = Sa[1]; Sa += 2; a++; Dt += 2;
}
for (int k = m; k < r; k++) zadd<LV>(W_R(S[2 * k + 1])); // and the whole RIGHT half
}
// ---- DESC fuse: the counter already holds all of L; sweep y descending, REMOVING each
// ---- left element as it is emitted. Ends with the counter empty. No inserts at all.
template <int LV> static void node_fused_desc(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
int ia = m - 1, ib = r - 1;
u64 *Dt = D + 2 * (r - 1); // ARM PTR: the destination cursor is a POINTER,
u64 *Sa = S + 2 * (m - 1), *Sb = S + 2 * (r - 1); // so the index t never has to exist
while (ia >= l && ib >= m) {
u64 w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if ((w0b >> 40) > (w0a >> 40)) { // descending: the LARGER y is emitted first; on a
w0b += zquery<LV>((u32)(w1b >> 40)); // y-tie the LEFT element goes first, mirroring ASC
Dt[0] = w0b; Dt[1] = w1b; Sb -= 2; ib--;
} else {
zsub<LV>((u32)((w1a >> 20) & 0xFFFFFu));
Dt[0] = w0a; Dt[1] = w1a; Sa -= 2; ia--;
}
Dt -= 2;
}
while (ib >= m) {
u32 c = zquery<LV>(W_T(Sb[1]));
Sb[0] += c;
Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb -= 2; ib--; Dt -= 2;
}
while (ia >= l) {
zsub<LV>(W_R(Sa[1]));
Dt[0] = Sa[0]; Dt[1] = Sa[1]; Sa -= 2; ia--; Dt -= 2;
}
}
// plain branchless y-merge (used for single-group nodes)
static void merge_run(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
int a = l, b = m, t = l;
while (a < m && b < r) {
int c = ((S[2 * a] >> 40) <= (S[2 * b] >> 40));
int s = c ? a : b;
D[2 * t] = S[2 * s]; D[2 * t + 1] = S[2 * s + 1];
a += c; b += 1 - c; t++;
}
while (a < m) { D[2 * t] = S[2 * a]; D[2 * t + 1] = S[2 * a + 1]; a++; t++; }
while (b < r) { D[2 * t] = S[2 * b]; D[2 * t + 1] = S[2 * b + 1]; b++; t++; }
}
// tie fallback: queries p with x==g (pass 2) / x!=g (pass 1), inserts q with x<g (pass 2)
template <int LV> static void cross_filter(int l, int m, int r, int src, u32 g, int pass) {
u64 *S = RC[src];
int i = l;
if (pass == 1) {
for (int j = m; j < r; j++) {
if (W_X(S[2 * j + 1]) == g) continue;
u32 yj = (u32)(S[2 * j] >> 40);
while (i < m && (u32)(S[2 * i] >> 40) < yj) { zadd<LV>(W_R(S[2 * i + 1])); i++; }
u32 c = zquery<LV>(W_T(S[2 * j + 1]));
if (c) S[2 * j] += c;
}
for (int k = l; k < i; k++) zsub<LV>(W_R(S[2 * k + 1]));
} else {
for (int j = m; j < r; j++) {
if (W_X(S[2 * j + 1]) != g) continue;
u32 yj = (u32)(S[2 * j] >> 40);
while (i < m && (u32)(S[2 * i] >> 40) < yj) {
if (W_X(S[2 * i + 1]) < g) zadd<LV>(W_R(S[2 * i + 1]));
i++;
}
u32 c = zquery<LV>(W_T(S[2 * j + 1]));
if (c) S[2 * j] += c;
}
for (int k = l; k < i; k++) if (W_X(S[2 * k + 1]) < g) zsub<LV>(W_R(S[2 * k + 1]));
}
}
#ifndef LEAF_N
#define LEAF_N 8
#endif
// base case: count all internal dominance pairs of a small x-group-aligned range
// directly, then insertion-sort the range by y. No counter, no recursion.
#define LSCR 512 // >= any LF; the leaf is processed entirely inside one call
static u32 lex[LSCR + 16], ley[LSCR + 16], ler[LSCR + 16];
static u64 lkey[LSCR + 16], ltmp[2 * (LSCR + 16)];
static u32 lk[256] __attribute__((aligned(32))); // bs path needs up to 256 keys
// ---- BITONIC MERGE of two sorted runs of n/2 keys (n = 128 or 256), branch-free -------
// In: k[0..n) with k[0..n/2) ascending and k[n/2..n) ascending.
// Out: k[0..n) ascending. Construction: reverse the top half so the array is a PEAK-shaped
// bitonic sequence, then Batcher's bitonic merger (distances n/2, n/4, ..., 1, min to the
// lower index). Every stage is a constant shuffle + min/max + blend.
static inline void bm(u32 *k, int n) {
const __m256i RIDX = _mm256_setr_epi32(7, 6, 5, 4, 3, 2, 1, 0);
{ // reverse the top half in place
for (int i = n / 2, j = n - 8; i < j; i += 8, j -= 8) {
__m256i a = _mm256_permutevar8x32_epi32(_mm256_loadu_si256((const __m256i *)(k + i)), RIDX);
__m256i b = _mm256_permutevar8x32_epi32(_mm256_loadu_si256((const __m256i *)(k + j)), RIDX);
_mm256_storeu_si256((__m256i *)(k + i), b);
_mm256_storeu_si256((__m256i *)(k + j), a);
}
if (n / 2 < n - 8 && (n / 2) % 8 == 0) { /* even split, handled above */ }
}
for (int d = n / 2; d >= 8; d >>= 1) { // register-to-register stages
for (int base = 0; base < n; base += 2 * d)
for (int j = 0; j < d; j += 8) {
__m256i a = _mm256_loadu_si256((const __m256i *)(k + base + j));
__m256i b = _mm256_loadu_si256((const __m256i *)(k + base + j + d));
_mm256_storeu_si256((__m256i *)(k + base + j), _mm256_min_epu32(a, b));
_mm256_storeu_si256((__m256i *)(k + base + j + d), _mm256_max_epu32(a, b));
}
}
for (int d = 4; d >= 1; d >>= 1) { // intra-register stages
__m256i idx = _mm256_setr_epi32(0^d, 1^d, 2^d, 3^d, 4^d, 5^d, 6^d, 7^d);
__m256i bsel = _mm256_setr_epi32((0&d)?-1:0, (1&d)?-1:0, (2&d)?-1:0, (3&d)?-1:0,
(4&d)?-1:0, (5&d)?-1:0, (6&d)?-1:0, (7&d)?-1:0);
for (int base = 0; base < n; base += 8) {
__m256i a = _mm256_loadu_si256((const __m256i *)(k + base));
__m256i q = _mm256_permutevar8x32_epi32(a, idx);
__m256i lo = _mm256_min_epu32(a, q), hi = _mm256_max_epu32(a, q);
_mm256_storeu_si256((__m256i *)(k + base), _mm256_blendv_epi8(lo, hi, bsel));
}
}
}
static inline void bs64(__m256i *r) {
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[2]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
{ __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[4]=Hi; }
{ __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[5]=Hi; }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[4]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[0], B=r[4]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[4]=Hi; }
{ __m256i A=r[1], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[5]=Hi; }
{ __m256i A=r[2], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[6]=Hi; }
{ __m256i A=r[3], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[7]=Hi; }
{ __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
{ __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[6]=Hi; }
{ __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[7]=Hi; }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[7]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
}
static int cdq_leaf(int l, int r, int in) {
u64 *S = RC[in];
const int sn = r - l;
for (int k = 0; k < sn; k++) { // compact u32 lanes in x-order (leaf is x-sorted)
u64 w0 = S[2 * (l + k)], w1 = S[2 * (l + k) + 1];
lex[k] = (u32)(w1 & 0xFFFFFu);
ley[k] = (u32)(w0 >> 40);
ler[k] = (u32)((w1 >> 20) & 0xFFFFFu);
}
for (int j = l + 1; j < r; j++) {
const int jl = j - l;
const u32 xj = W_X(S[2 * j + 1]), yj = (u32)(S[2 * j] >> 40), tj = W_T(S[2 * j + 1]);
const __m256i mxj = _mm256_set1_epi32((int)xj);
const __m256i myj = _mm256_set1_epi32((int)yj);
const __m256i mtj = _mm256_set1_epi32((int)tj);
u32 acc = 0;
int k = 0;
for (; k + 8 <= jl; k += 8) { // all values < 2^20, so signed cmps are exact
__m256i c = _mm256_and_si256(_mm256_cmpgt_epi32(mxj, _mm256_loadu_si256((const __m256i *)(lex + k))),
_mm256_and_si256(_mm256_cmpgt_epi32(myj, _mm256_loadu_si256((const __m256i *)(ley + k))),
_mm256_cmpgt_epi32(mtj, _mm256_loadu_si256((const __m256i *)(ler + k)))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(c)));
}
if (k < jl) {
__m256i cc = _mm256_and_si256(_mm256_cmpgt_epi32(mxj, _mm256_loadu_si256((const __m256i *)(lex + k))),
_mm256_and_si256(_mm256_cmpgt_epi32(myj, _mm256_loadu_si256((const __m256i *)(ley + k))),
_mm256_cmpgt_epi32(mtj, _mm256_loadu_si256((const __m256i *)(ler + k)))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(cc)) & ((1u << (jl - k)) - 1));
}
S[2 * j] += acc;
}
{ // y-sort: AVX2 bitonic sort of packed u32 keys, then one permute
if (sn <= 64) {
for (int k = 0; k < sn; k++) lk[k] = (ley[k] << 8) | (u32)k;
for (int k = sn; k < 64; k++) lk[k] = 0xFFFFFFFFu;
{
__m256i r[8];
for (int q = 0; q < 8; q++) r[q] = _mm256_load_si256((const __m256i *)(lk + 8 * q));
bs64(r);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(lk + 8 * q), r[q]);
}
for (int k = 0; k < sn; k++) {
const int sr = (int)(lk[k] & 127u);
ltmp[2 * k] = S[2 * (l + sr)]; ltmp[2 * k + 1] = S[2 * (l + sr) + 1];
}
} else {
// sn in (64,256]: sort each 64-key block with the fixed network, then merge pairwise.
// sn in (64,256] -> 128 or 256 keys, PADDED TO THE FULL WIDTH so every merged span is
// fully initialised (a 3-block span would otherwise expose stale keys from a prior call).
const int lim = (sn <= 128) ? 128 : 256; // power of two, each a tree of bm()'s
const int nb = lim >> 6;
for (int k = 0; k < sn; k++) lk[k] = (ley[k] << 8) | (u32)k;
for (int k = sn; k < lim; k++) lk[k] = 0xFFFFFFFFu;
for (int b = 0; b < nb; b++) {
__m256i r[8];
for (int q = 0; q < 8; q++) r[q] = _mm256_load_si256((const __m256i *)(lk + 64 * b + 8 * q));
bs64(r);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(lk + 64 * b + 8 * q), r[q]);
}
if (nb == 2) bm(lk, 128);
else { bm(lk, 128); bm(lk + 128, 128); bm(lk, 256); }
for (int k = 0; k < sn; k++) {
const int sr = (int)(lk[k] & 255u);
ltmp[2 * k] = S[2 * (l + sr)]; ltmp[2 * k + 1] = S[2 * (l + sr) + 1];
}
}
for (int k = 0; k < sn; k++) { S[2 * (l + k)] = ltmp[2 * k]; S[2 * (l + k) + 1] = ltmp[2 * k + 1]; }
}
return in;
}
// returns the buffer holding the y-sorted range [l,r)
// FULL==0: leaves the rank counter EMPTY. FULL==1: leaves [l,r) fully INSERTED.
template <int LV, int LF, int FULL> static int cdq(int l, int r, int in) {
int s = r - l;
if (s <= 1) return in;
if (s <= LF) {
int bb = cdq_leaf(l, r, in);
if (FULL) { u64 *Q = RC[bb]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return bb;
}
int m = (l + r) >> 1;
int mode = 3;
const u64 *SI = RC[in];
if (__builtin_expect(W_X(SI[2 * m - 1]) != W_X(SI[2 * m + 1]), 1)) mode = 0;
else {
u32 g = W_X(SI[2 * m + 1]);
int a = m - 1; while (a > l && W_X(SI[2 * a - 1]) == W_X(SI[2 * a + 1])) a--;
int b = m; while (b < r && W_X(SI[2 * b - 1]) == W_X(SI[2 * b + 1])) b++;
if (a == l && b == r) mode = 2;
else {
int lim = s >> 2;
int ca = -1, cb = -1;
if (a > l && a - l >= lim && r - a >= lim) ca = a;
if (b < r && b - l >= lim && r - b >= lim) cb = b;
if (ca >= 0 && (cb < 0 || m - ca <= cb - m)) { m = ca; mode = 1; }
else if (cb >= 0) { m = cb; mode = 1; }
}
}
if (FULL == 0 && (mode == 0 || mode == 1)) {
// RIGHT child first (must end empty), then the LEFT child (ends holding all of [l,m)),
// then a descending fuse that CONSUMES it. No undo anywhere in this node.
int b2 = cdq<LV, LF, 0>(m, r, in);
int b1 = cdq<LV, LF, 1>(l, m, in);
if (b1 != b2) {
memcpy(RC[b1] + 2 * m, RC[b2] + 2 * m, (size_t)(r - m) * 16);
b2 = b1;
}
int out = 1 - b1;
node_fused_desc<LV>(l, m, r, b1, out);
return out;
}
int b1 = cdq<LV, LF, 0>(l, m, in);
int b2 = cdq<LV, LF, 0>(m, r, in);
if (b1 != b2) {
memcpy(RC[b1] + 2 * m, RC[b2] + 2 * m, (size_t)(r - m) * 16);
b2 = b1;
}
if (mode == 0 || mode == 1) {
int out = 1 - b1;
if (FULL) { node_fused_full<LV>(l, m, r, b1, out); return out; }
node_fused<LV>(l, m, r, b1, out);
return out;
}
if (mode == 2) {
int out = 1 - b1;
merge_run(l, m, r, b1, out);
if (FULL) { u64 *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return out;
}
// mode 3: x-tie spans the midpoint, no balanced group boundary: filtered passes
{
const u64 *S = RC[b1];
u32 g = 0;
for (int k = l; k < m; k++) { u32 xv = W_X(S[2 * k + 1]); if (xv > g) g = xv; }
cross_filter<LV>(l, m, r, b1, g, 1);
cross_filter<LV>(l, m, r, b1, g, 2);
}
int out = 1 - b1;
merge_run(l, m, r, b1, out);
if (FULL) { u64 *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return out;
}
void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
if (n <= 1) { if (n == 1) out[0] = 0; return; }
msk_init();
// ---- z compression: T = #{z' < z}, R = unique rank in z order ----
memset(H32, 0, (size_t)(n + 1) * 4);
for (int i = 0; i < n; i++) {
u32 h = H32[z[i]];
if ((h & 0xFFFu) != 0xFFFu) H32[z[i]] = h + 1; // clamp: never carry into the start field
}
{
u32 acc = 0;
for (int v = 0; v <= n; v++) { u32 c = H32[v] & 0xFFFu; H32[v] = acc << 12; acc += c; }
}
// ---- build pre-records (final layout, A=0) + x histogram ----
memset(CNT, 0, (size_t)(n + 1) * 4);
for (int i = 0; i < n; i++) {
if (i + 48 < n) __builtin_prefetch(&H32[z[i + 48]]);
u32 zv = z[i];
u32 h = H32[zv];
u32 T = h >> 12;
u32 R = T + (h & 0xFFFu);
if ((h & 0xFFFu) != 0xFFFu) H32[zv] = h + 1;
P1[i] = ((u64)T << 40) | ((u64)R << 20) | (u64)x[i];
}
// ---- RADIX placement by x: 1024-bucket histogram (4 KB, L1) + a scatter into 1024 contiguous
// ---- bucket regions (~64 KB of hot lines, L2) + a per-bucket counting sort on the low 10 bits.
// ---- BOTH passes are STABLE, so the x-order AND the input-order tie break are identical to the
// ---- old `CNT[x[i]]++` counting sort => byte-exact. x < n <= 1e6 < 2^20, so x>>10 < 1024.
static u64 SCT[2 * MAXN];
static u32 ST10[1025];
static u16 C16[1024];
memset(CNT, 0, 1024 * 4);
for (int i = 0; i < n; i++) {
if (i + 16 < n) __builtin_prefetch(&CNT[x[i + 16] >> 10]);
CNT[x[i] >> 10]++;
}
{
u32 acc = 0;
for (int v = 0; v < 1024; v++) { u32 c = CNT[v]; ST10[v] = acc; CNT[v] = acc; acc += c; }
ST10[1024] = acc;
}
for (int i = 0; i < n; i++) {
if (i + 96 < n) { __builtin_prefetch(&CNT[x[i + 96] >> 10]);
__builtin_prefetch(&SCT[2 * (size_t)CNT[x[i + 96] >> 10]]); }
const u32 t = CNT[x[i] >> 10]++;
_mm_storeu_si128((__m128i *)(void *)(SCT + 2 * t),
_mm_set_epi64x((long long)P1[i], (long long)(((u64)y[i] << 40) | ((u64)i << 20))));
}
{
u64 *D = RC[0];
for (int b = 0; b < 1024; b++) {
const int lo = (int)ST10[b], hi = (int)ST10[b + 1];
if (hi <= lo) continue;
memset(C16, 0, 1024 * 2);
for (int t = lo; t < hi; t++) C16[SCT[2 * t + 1] & 1023u]++;
u32 acc2 = 0;
for (int v = 0; v < 1024; v++) { u16 c = C16[v]; C16[v] = (u16)acc2; acc2 += c; }
for (int t = lo; t < hi; t++) {
const u32 p = (u32)lo + (u32)C16[SCT[2 * t + 1] & 1023u]++;
_mm_storeu_si128((__m128i *)(void *)(D + 2 * p),
_mm_loadu_si128((const __m128i *)(const void *)(SCT + 2 * t)));
}
}
}
// ---- tie bits over x-order positions ----
// ---- CDQ ----
// (ENGINE, SIZE)-dependent: measured optima are LF=16 at n=1e5 and LF=24 at n=1e6.
int bb = (n <= 262144) ? cdq<3, 64, 0>(0, n, 0) : cdq<4, 256, 0>(0, n, 0);
{
const u64 *D = RC[bb];
for (int p = 0; p < n; p++) {
if (p + 32 < n) __builtin_prefetch(&out[W_ORIG(D[2 * (p + 32)])]);
out[W_ORIG(D[2 * p])] = W_A(D[2 * p]);
}
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 139.098 ms | 57 MB + 400 KB | Accepted | Score: 100 | 显示更多 |