// 1008e8 -- 2D dominance counting, n = 1e8: out[i] = #{j: x[j]<x[i] and y[j]<y[i]}
//
// v6 = v5's memory-fitted design with the random y gathers removed. On the judge
// v5 was AC at 14.263 s, and a variant whose gather was replaced by a cheap hash
// of idx ran 6.207 s -- so ~8 s of v5 was 1e8 random reads into the 400 MB y
// array (4 KB pages -> TLB miss + page walk on almost every one). Here y is
// permuted in lockstep with the x radix sort (an extra 4-byte stream per pass,
// ~2.4 GB of extra traffic in total, far cheaper than the gathers).
//
// The problem is split by the y median so each half fits:
// y_i < K : out[i] = #{j: y_j<y_i, x_j<x_i} (all such j are low)
// y_i >= K : out[i] = #{j low: x_j < x_i} + #{j high: y_j<y_i, x_j<x_i}
// The cross term is one sequential merge of the two x-sorted key arrays.
//
// Record encoding
// during split/sort : [spare:11 | idx:27 | x:27] (x in the low bits)
// after attach : [cnt:11 | idx:27 | y:26] (y shifted into [0,2^26))
// The per-element count is 27 bits: 11 in the record + the top 16 in a u16 array,
// so every count travels with its element and out[] never receives a random RMW.
//
// Buffers (M = n/2 + slack): RA,RB,RC u64[M] (~400 MB each), Y1,Y2 u32[M]
// (~200 MB each), U1 u16[M] (100 MB) = ~1.66 GB of our own, plus the tasklib's
// out (400 MB) which holds the answers (and nothing else).
#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <sys/mman.h>
#include <immintrin.h>
#include <cstdio>
#include <time.h>
#define PHN 12
static double g_ph[PHN]; static const char *g_pn[PHN]={"splitA","sort_xA","attachA","levelsA","emitA","splitB","sort_xB","cross","attachB","levelsB","emitB","TOTAL"};
static inline double phnow(){struct timespec t;clock_gettime(CLOCK_MONOTONIC,&t);return t.tv_sec+t.tv_nsec*1e-9;}
void phdump(){for(int i=0;i<PHN;i++)fprintf(stderr,"PHASE %-9s %8.3f s\n",g_pn[i],g_ph[i]);}
#ifndef NO_AVX2
#pragma GCC push_options
#pragma GCC target("avx2")
#endif
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
static const u64 M27 = 0x7FFFFFFull;
static const u64 LOW53 = 0x1FFFFFFFFFFFFFull; // idx:27 | y:26
static u64 *RA, *RB, *RC;
static u32 *Y1, *Y2;
static u16 *U1;
static size_t gCap;
static const unsigned *gX, *gY;
static unsigned *gOut;
static u32 gCnt[4096];
static u32 gH1[512]; // L1-digit histogram, built during the split sweep
static u32 gNxt[512]; // histogram of the NEXT radix pass, built during the current scatter
static u32 gBndL2[520]; // L2 bucket boundaries inside the current L1 bucket
static u32 gBndL1[520];
static size_t gOutLim = 0;
static u32 gCur[4096];
static u32 gIdxH[1032]; // SC1-B: idx digit = idx>>17, 1024 buckets
static u32 gIdxCur[1024]; // per-idx-digit write cursor
static u32 gBnd2[512][513]; // per-L1-bucket L2 boundaries (phase split)
// ---- branchless 8x8x8 cumulative digit counter: query = 3 loads, insert = 3
// masked SIMD suffix adds over 8-lane u32; 2 KB of state, all L1 resident.
static u32 gP1[8];
static u32 gP2[8][8];
static u32 gP3[8][8][8];
static u32 gMsk[8][8] __attribute__((aligned(32)));
static int gMskInit = 0;
static inline void cnt_init(void) {
if (!gMskInit) {
for (u32 m = 0; m < 8; m++)
for (u32 i = 0; i < 8; i++) gMsk[m][i] = (i > m);
gMskInit = 1;
}
memset(gP1, 0, sizeof(gP1));
memset(gP2, 0, sizeof(gP2));
memset(gP3, 0, sizeof(gP3));
}
static inline u32 cnt_q(u32 d) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
return gP1[a] + gP2[a][b] + gP3[a][b][c];
}
static inline void cnt_ins(u32 d) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
__m256i one = _mm256_set1_epi32(1);
__m256i m3 = _mm256_load_si256((const __m256i *)gMsk[c]);
__m256i v3 = _mm256_loadu_si256((const __m256i *)&gP3[a][b][0]);
_mm256_storeu_si256((__m256i *)&gP3[a][b][0],
_mm256_add_epi32(v3, _mm256_and_si256(m3, one)));
__m256i m2 = _mm256_load_si256((const __m256i *)gMsk[b]);
__m256i v2 = _mm256_loadu_si256((const __m256i *)&gP2[a][0]);
_mm256_storeu_si256((__m256i *)&gP2[a][0],
_mm256_add_epi32(v2, _mm256_and_si256(m2, one)));
__m256i m1 = _mm256_load_si256((const __m256i *)gMsk[a]);
__m256i v1 = _mm256_loadu_si256((const __m256i *)&gP1[0]);
_mm256_storeu_si256((__m256i *)&gP1[0],
_mm256_add_epi32(v1, _mm256_and_si256(m1, one)));
}
// CI4: ported from the SIBLING row 1008 (which boards this; 1008e8 did not carry it).
// The top counter level is held in a YMM register and queried with vpermd, so the
// per-element 4-byte load from a just-written 32-byte store (store->load-forward
// failure) disappears, as does the 32-byte store itself.
static inline u32 lane8(__m256i v, u32 a) {
__m256i sel = _mm256_permutevar8x32_epi32(v, _mm256_set1_epi32((int)a));
return (u32)_mm_cvtsi128_si32(_mm256_castsi256_si128(sel));
}
static inline u32 cnt_qv(u32 d, __m256i P1v) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
return lane8(P1v, a) + gP2[a][b] + gP3[a][b][c];
}
static inline void cnt_insv(u32 d, __m256i &P1v) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
__m256i one = _mm256_set1_epi32(1);
__m256i m3 = _mm256_load_si256((const __m256i *)gMsk[c]);
__m256i v3 = _mm256_loadu_si256((const __m256i *)&gP3[a][b][0]);
_mm256_storeu_si256((__m256i *)&gP3[a][b][0], _mm256_add_epi32(v3, _mm256_and_si256(m3, one)));
__m256i m2 = _mm256_load_si256((const __m256i *)gMsk[b]);
__m256i v2 = _mm256_loadu_si256((const __m256i *)&gP2[a][0]);
_mm256_storeu_si256((__m256i *)&gP2[a][0], _mm256_add_epi32(v2, _mm256_and_si256(m2, one)));
P1v = _mm256_add_epi32(P1v, _mm256_and_si256(_mm256_load_si256((const __m256i *)gMsk[a]), one));
}
static void *bigalloc(size_t bytes) {
void *p = mmap(0, bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (p != MAP_FAILED) return p; // mmap fails on JudgeDuck -> malloc
return malloc(bytes);
}
// ------------------------------------------------------------------
// 3-pass LSD radix sort by x of [spare:11|idx:27|x:27] records, permuting the
// parallel y array with the identical permutation; the result ends in X1 / Yb.
//
// ARM: the histogram of each pass is DERIVED DURING THE PREVIOUS PASS'S SCATTER,
// where the record is already in a register -- the three standalone histogram
// sweeps over the records are gone. Pass 1's histogram must be supplied by the
// caller, which has x[i] in hand while it is already building the record.
static void sort_x(u64 *X0, u64 *X1, u32 *Ya, u32 *Yb, size_t m) {
// ---- pass 1: gCnt must already hold the histogram of (X0[i] & 511) ----
gCur[0] = 0;
for (u32 b = 1; b < 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
memset(gNxt, 0, sizeof(gNxt));
for (size_t i = 0; i < m; i++) {
u64 rec = X0[i];
u32 q = gCur[(u32)rec & 511u]++;
X1[q] = rec;
Yb[q] = Ya[i];
gNxt[(u32)(rec >> 9) & 511u]++;
}
// ---- pass 2: gCnt <- gNxt (histogram of X1 >> 9), build pass 3's histogram ----
memcpy(gCnt, gNxt, sizeof(gNxt));
gCur[0] = 0;
for (u32 b = 1; b < 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
memset(gNxt, 0, sizeof(gNxt));
for (size_t i = 0; i < m; i++) {
u64 rec = X1[i];
u32 q = gCur[(u32)(rec >> 9) & 511u]++;
X0[q] = rec;
Ya[q] = Yb[i];
gNxt[(u32)(rec >> 18) & 511u]++;
}
// ---- pass 3: gCnt <- gNxt (histogram of X0 >> 18) ----
memcpy(gCnt, gNxt, sizeof(gNxt));
gCur[0] = 0;
for (u32 b = 1; b < 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
for (size_t i = 0; i < m; i++) {
u64 rec = X0[i];
u32 q = gCur[(u32)(rec >> 18) & 511u]++;
X1[q] = rec;
Yb[q] = Ya[i];
}
}
// ------------------------------------------------------------------
// y is already in sequence order (Yv); fold the x-tie correction into the 27-bit
// count, rewrite the record as [cnt:11|idx:27|y:26], histogram y's top digit.
// `preseed` = the count already holds the half's cross term (high half).
// ------------------------------------------------------------------
// FUSED attach + L1. The old code wrote an intermediate record
// [cnt:11|idx:27|y:26] into X, and levels()'s L1 pass read the WHOLE array back to
// scatter it into the L1 layout. Both the write and the read-back are gone: the two
// sweeps walked the same array in the same order, so the correction and the scatter
// belong in one loop. Per half this deletes ~911 MB of traffic at n=1e8.
static void attach_l1(u64 *X, const u32 *Yv, u32 *Xout, u64 *Dst, u16 *Cb,
size_t m, int preseed) {
gCur[0] = 0;
for (u32 b = 1; b <= 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
for (u32 b = 0; b <= 512; b++) gBndL1[b] = gCur[b];
cnt_init();
// CI4 (port of sibling 1008's single-pass fusion): the x-group boundary is found by
// the element that CHANGES xv, so the separate q-scan (one dependent load+mask+cmp+
// branch per element over the whole array) is deleted. `gstart` replaces the group
// base; the dup loop still runs over exactly [group_start, a).
__m256i P1v = _mm256_setzero_si256();
size_t gstart = 0;
u64 prev_xv = ~(u64)0;
for (size_t a = 0; a < m; a++) {
u64 rec = X[a];
u64 xv = rec & M27;
if (xv != prev_xv) { gstart = a; prev_xv = xv; }
u32 ia = (u32)((rec >> 27) & M27);
u32 xvv = (u32)rec & (u32)M27;
u32 ya = Yv[a];
u32 dup = 0;
if (a > gstart) { for (size_t b = gstart; b < a; b++) dup += (Yv[b] < ya); }
u32 cnt = preseed ? ((u32)(rec >> 54) | ((u32)U1[a] << 10)) : 0u;
cnt = (cnt - dup) & 0x7FFFFFFu;
if (Xout) Xout[a] = xvv;
u32 d1 = (ya >> 17) & 511u;
cnt = (cnt + cnt_qv(d1, P1v)) & 0x7FFFFFFu;
cnt_insv(d1, P1v);
u32 qq = gCur[d1]++;
Dst[qq] = ((u64)(cnt & 0xFFFFFu) << 44) | ((u64)((ya >> 8) & 511u) << 35) |
((u64)(ya & 255u) << 27) | (u64)ia;
Cb[qq] = (u16)(cnt >> 20);
}
}
// ------------------------------------------------------------------
// Two-pass MSD rank accumulation over the 26-bit y field (digits 9/9/8), with the
// last two digits resolved inside the L1 bucket (L1 cache resident) and out[] stored
// directly. Replaces sol_v6's four-pass L1/L2/L3/L4 chain.
//
// incoming (from attach): X0[t] = [cnt:11 @53..63 | idx:27 @26..52 | y:26 @0..25],
// Ca[t] = cnt >> 11 (array is x-sorted)
// working layout: [cntlo:20 @44..63 | d2:9 @35..43 | d3:8 @27..34 | idx:27 @0..26]
// side[q] = cnt >> 20 (low byte of the u16 side array)
// count <= n-1 < 2^27 => 20 + 8 bits is enough.
static void levels(u64 *X0, u64 *X1, u16 *Ca, u16 *Cb, size_t m, unsigned *out) {
// ---------------- L1 is done by attach_l1; L2 + L3 follow ----------
// ARM (lane l1008e8_1002): the L3 pass used to end in `out[idx] = cnt`, i.e.
// 1e8 random 4-byte stores into the 400 MB output array. Here the half is
// split into 512 buckets by the TOP 9 BITS OF idx (a digit the record already
// carried) and the L3 pass scatters (cnt<<27|idx) into those buckets instead.
// The global idx-digit histogram is built DURING the L2 histogram sweep (the
// record is in a register for free), so the split costs one extra 512-entry
// array, not an extra pass. The emit then walks the buckets in increasing idx
// order: 512 monotone windows of 195 313 slots, no page walk and no RFO storm.
memset(gIdxH, 0, sizeof(gIdxH));
// ---- phase A: L2 for every L1 bucket, plus the idx-digit histogram ----------
for (u32 b0 = 0; b0 < 512; b0++) {
size_t s = gBndL1[b0], e = gBndL1[b0 + 1];
if (e - s <= 1) {
if (e > s) { gIdxH[(u32)(X1[s] >> 17) & 1023u]++;
u32 c0 = ((u32)(X1[s] >> 44) | ((u32)Cb[s] << 20)) & 0x7FFFFFFu;
X0[s] = ((u64)c0 << 35) | (X1[s] & 0x00000007FFFFFFFFull); }
gBnd2[b0][0] = s; gBnd2[b0][1] = e;
continue;
}
// L2: histogram the d2 digit (bits 35..43) of this bucket
memset(gCnt, 0, 512 * sizeof(u32));
for (size_t t = s; t < e; t++) { u64 rc = X1[t];
gCnt[(u32)(rc >> 35) & 511u]++;
gIdxH[(u32)(rc >> 17) & 1023u]++; }
gCur[0] = 0;
for (u32 b = 1; b <= 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
for (u32 b = 0; b <= 512; b++) gBnd2[b0][b] = s + gCur[b];
cnt_init();
__m256i P1v = _mm256_setzero_si256();
for (size_t t = s; t < e; t++) {
u64 rec = X1[t];
u32 d2 = (u32)(rec >> 35) & 511u;
u32 inc = cnt_qv(d2, P1v);
cnt_insv(d2, P1v);
u32 q = s + gCur[d2]++;
u32 cnt = (((u32)(rec >> 44) | ((u32)Cb[t] << 20)) + inc) & 0x7FFFFFFu;
/* keep d2(35..43), d3(27..34), idx(0..26) -- L3 run-keys on d2 */
X0[q] = ((u64)cnt << 35) | (rec & 0x00000007FFFFFFFFull);
}
}
// ---- prefix the idx-digit histogram; X1 is dead from here on ---------------
{ u32 run = 0;
for (u32 b = 0; b < 1024; b++) { u32 c = gIdxH[b]; gIdxCur[b] = run; run += c; } }
// ---- phase B: L3 for every L1 bucket, scattered 8 B into X1 (the idx bucket)
for (u32 b0 = 0; b0 < 512; b0++) {
size_t s = gBndL1[b0], e = gBndL1[b0 + 1];
if (e - s <= 1) {
if (e > s) { u64 rc = X0[s];
X1[gIdxCur[(u32)(rc >> 17) & 1023u]++] = rc; }
continue;
}
// L3 inside X0[s..e): runs of equal d2, digit d3 (bits 27..34).
for (u32 d2 = 0; d2 < 512; d2++) {
size_t p = gBnd2[b0][d2], qq = gBnd2[b0][d2 + 1];
if (qq <= p) continue;
if (qq - p == 1) {
u32 c0 = ((u32)(X0[p] >> 35)) & 0x7FFFFFFu;
X1[gIdxCur[(u32)(X0[p] >> 17) & 1023u]++] = ((u64)c0 << 27) | (X0[p] & M27);
} else {
cnt_init();
__m256i P1v = _mm256_setzero_si256();
for (size_t a = p; a < qq; a++) {
u64 rec = X0[a];
u32 d3 = (u32)(rec >> 27) & 255u;
u32 inc = cnt_qv(d3, P1v);
cnt_insv(d3, P1v);
u32 cnt = ((u32)(rec >> 35) + inc) & 0x7FFFFFFu;
X1[gIdxCur[(u32)(rec >> 17) & 1023u]++] = ((u64)cnt << 27) | (rec & M27);
}
}
}
}
}
// ARM: the emit. gIdxCur[b] now holds the END of idx-bucket b (it started at the
// bucket's prefix offset and was advanced once per element), so the buckets are
// already laid out in increasing idx order and out[] is filled by one forward sweep.
static void emit_idx_buckets(const u64 *Xb, size_t m, unsigned *out) {
size_t p = 0;
for (u32 b = 0; b < 1024; b++) {
size_t q = gIdxCur[b];
for (; p < q; p++) out[(u32)(Xb[p] & M27)] = (u32)(Xb[p] >> 27);
}
}
// ------------------------------------------------------------------
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
double _t0=phnow();
if (n <= 0) return;
if (n == 1) { out[0] = 0; return; }
if (n <= 2000) {
memset(out, 0, (size_t)n * 4);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (x[j] < x[i] && y[j] < y[i]) out[i]++;
return;
}
size_t N = (size_t)n;
size_t M = N / 2 + 70000; // slack for the cut granularity
if (gCap < M) {
if (RA) { munmap(RA, gCap * 8); munmap(RB, gCap * 8); munmap(RC, gCap * 8); }
if (Y1) { munmap(Y1, gCap * 4); munmap(Y2, gCap * 4); }
if (U1) munmap(U1, gCap * 2);
RA = (u64 *)bigalloc(M * 8);
RB = (u64 *)bigalloc(M * 8);
RC = (u64 *)bigalloc(M * 8);
Y1 = (u32 *)bigalloc(M * 4);
Y2 = (u32 *)bigalloc(M * 4);
U1 = (u16 *)bigalloc(M * 2);
gCap = M;
if (!RA || !RB || !RC || !Y1 || !Y2 || !U1) { gCap = 0; return; }
}
gX = x; gY = y; gOut = out; gOutLim = N;
// ---- choose the y cut K: exact bucket boundaries over the top 11 bits of y
static u32 hist[2048];
memset(hist, 0, sizeof(hist));
for (size_t i = 0; i < N; i++) hist[y[i] >> 16]++;
size_t want = N / 2, acc = 0;
u32 K = 0;
for (u32 b = 0; b < 2048; b++) {
acc += hist[b];
if (acc >= want) { K = (b + 1) << 16; break; }
}
if (K == 0) K = 1u << 16;
size_t lo = acc, hi = N - acc;
// constraints: both halves fit their buffers, the high half fits out (8 bytes
// per record in 4 bytes per element), and both y ranges fit the 26-bit field
if (hi == 0 || lo >= M || hi > N / 2 || hi >= M || (u64)K > (1u << 26) ||
(u64)(N - K) > (1u << 26)) {
memset(out, 0, N * 4); // pathological input: bail out
for (size_t i = 0; i < N; i++)
for (size_t j = 0; j < N; j++)
if (x[j] < x[i] && y[j] < y[i]) out[i]++;
return;
}
// ---- split A: low half -> RA (records) / Y1 (y, in the same order)
{
size_t a = 0; double _t = phnow();
memset(gCnt, 0, 512 * sizeof(u32)); // pass-1 histogram for sort_x below
memset(gH1, 0, sizeof(gH1)); // L1-digit histogram for the fused sweep
for (size_t i = 0; i < N; i++) { // BW12 BR1: branchless compaction
unsigned xi = x[i], yi = y[i], take = (yi < K);
RA[a] = ((u64)i << 27) | (u64)xi; // unconditional, sequential
Y1[a] = yi;
a += take;
gCnt[xi & 511u] += take; // 2 KB / 2 KB, both L1-resident
gH1[(yi >> 17) & 511u] += take;
}
g_ph[0]+=phnow()-_t; }
// ---- low half: x sort (records -> RC, y -> Y2)
{ double _t=phnow();
sort_x(RA, RC, Y1, Y2, lo);
g_ph[1]+=phnow()-_t; }
// the low half's sorted x values are emitted by attach() itself (Y1 is free
// after sort_x's pass 3); the standalone copy sweep is gone
memcpy(gCnt, gH1, sizeof(gH1));
{ double _t=phnow();
attach_l1(RC, Y2, Y1, RA, (u16 *)RB, lo, 0);
g_ph[2]+=phnow()-_t; }
{ double _t=phnow();
levels(RC, RA, U1, (u16 *)RB, lo, out); // low half: buckets of (cnt,idx) in RA
g_ph[3]+=phnow()-_t; }
{ double _t=phnow();
emit_idx_buckets(RA, lo, out); // monotone sweep -> out
g_ph[4]+=phnow()-_t; }
// ---- split B: high half -> RB (records) / Y2 (y shifted into [0,2^26))
{
size_t b = 0; double _t = phnow();
memset(gCnt, 0, 512 * sizeof(u32)); // pass-1 histogram for sort_x below
memset(gH1, 0, sizeof(gH1)); // L1-digit histogram for the fused sweep
for (size_t i = 0; i < N; i++) { // BW12 BR1: branchless compaction
unsigned xi = x[i], yi = y[i], take = (yi >= K);
RB[b] = ((u64)i << 27) | (u64)xi;
Y2[b] = yi - K;
b += take;
gCnt[xi & 511u] += take;
gH1[((yi - K) >> 17) & 511u] += take;
}
g_ph[5]+=phnow()-_t; }
// ---- high half: x sort (records -> RC, y -> RA reused as a u32 buffer)
{ double _t=phnow();
sort_x(RB, RC, Y2, (u32 *)RA, hi);
g_ph[6]+=phnow()-_t; }
// ---- cross term: #{low: x_j < x_i} for every high element, one merge sweep
{
size_t a = 0; u32 run = 0; double _tc = phnow();
for (size_t b = 0; b < hi; b++) {
u64 rec = RC[b];
u32 xb = (u32)rec & (u32)M27;
// BW12 CX1: the merge advance was a ~50/50 unpredictable branch (both sequences
// sorted, x and y independent). Advance by up to 8 per step with one SIMD compare;
// the leftover is finished by the scalar loop, so the result is identical.
{ const __m256i xv = _mm256_set1_epi32((int)xb);
while (a + 8 <= lo) {
__m256i yv = _mm256_loadu_si256((const __m256i *)(Y1 + a));
unsigned msk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(xv, yv)));
unsigned adv = (unsigned)__builtin_popcount(msk);
a += adv; run += adv;
if (adv < 8u) break; // one branch per 8 elements, and it is predictable
} }
while (a < lo && Y1[a] < xb) { a++; run++; }
RC[b] = rec | ((u64)(run & 1023u) << 54); // low 10 bits into the record
U1[b] = (u16)(run >> 10); // the top 16 into U1
}
g_ph[7]+=phnow()-_tc; }
memcpy(gCnt, gH1, sizeof(gH1));
{ double _t=phnow();
attach_l1(RC, (u32 *)RA, (u32 *)0, RB, (u16 *)Y1, hi, 1);
g_ph[8]+=phnow()-_t; }
{ double _t=phnow();
levels(RC, RB, U1, (u16 *)Y1, hi, out); // high half: buckets of (cnt,idx) in RB
g_ph[9]+=phnow()-_t; }
{ double _t=phnow();
emit_idx_buckets(RB, hi, out);
g_ph[10]+=phnow()-_t; } // monotone sweep -> out
g_ph[11]+=phnow()-_t0; phdump();
}