代码

// ===== REFERENCES =====
// [1] 本账号 saffah_cc_v41_agg1，提交 **#102821** <https://duck.ac/submission/102821>
//     （**26.864711 ms = 我方当值最好件 = 本题 `mine`**）—— **本件正文的逐字节基座**，
//     除本发唯一改动（[HOIST3] 一段纯重排）外一字未改。它本身 = #102694 + [HOIST] + [HOIST2]。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 **#107209**（本题实时 T = 26.571198 ms）。
//     本发不取它的任何一行；仅按 `tools/exact.py` 取口径。
// [3] duck.ac 题目页 <https://duck.ac/problem/noip17f>。
//     口径（本席自核）：mine=26.864711 · T=26.571198 · **严支真靶 = 0.99*T+1µs = 26.306486 ms
//     ⇒ 本发前还差 0.558225 ms（2.078%）** ✓
// [4] /home/yjp/duck.ac/BRIEF.md **`§2.19.678`**（"删工作"面封死 ≠ "调度/流水"面封死；绑定是延迟/端口饥饿
//     ⇒ 做排程）+ 本题 notes 尾部**预登记计划**（"若再次翻红：第一顺位是同一根轴上的下一处 pc 无关工作
//     （类 2 的 `pp`/`val` 预计算、**`RAPP` 读**、`CAPP5` 值的预备）"）—— 本发正是该顺位的第二项。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【本发只有一个变量：[HOIST3] —— 把 `pp` 与惰性 `RAPP` 读 + `resolve` 提到列选择链之前（**纯重排**）】
//
// ① 为什么这是同一条轴上的下一处（承接 [HOIST] −0.654% 与 [HOIST2] −2.65%）：
//    本引擎的绑定是**依赖链**（332 条 / ~240 uop vs 223 周期/查询 ⇒ IPC ≈ 1.05），标定已证
//    "省 uop 不兑现、加东西必亏、**只有缩短/重叠链才兑现**"。上一刀把 `small_remove`/`kth_alive_del`
//    提到了列选择之前；本刀接着把**同一段 pc 无关工作**里剩下的两项也提前。
// ② pc 无关性的证明（地址只依赖 [HOIST]/[HOIST2] 已提前的读）：
//    `pp = hopp`（[HOIST2] 已经算好）；`ro = hoffb & 0x7FFFF`、`ap = happn`（[HOIST] 已经读好）。
//    ⇒ 惰性读的地址 `RAPP + ro + (pp - m)` 与 `resolve(...)` 的输入**完全不含 `pc`** ✓
// ③ 重排而非增删：提前算出的 `hpp`/`hrv` 就在原处被**直接使用**（原地替换原表达式），
//    ⇒ 编译器 CSE 后指令数不变（本发正文净增 0 条有效指令，只多 2 个变量的活跃区间）。
// ④ 次序安全：`RAPP[ro+ap] = pc` 这个**写**仍留在列选择之后 ⇒ **同一迭代内"先读后写"的次序逐字保留**，
//    跨迭代也未被提前（与 [HOIST]/[HOIST2] 同一处理）；`chk` 逐位相同佐证 ✓
// ⑤ 判题机证据（**立即体验，生产几何 n=m=q=3e5，同进程两变体 × 3 轮取 min**）：
//      base  min=82,473,434 tick   loop=61,804,148   +0.000%   chk=d2937ba3ddba1bdc
//      h3    min=80,193,326 tick   loop=59,763,776   **−2.765%**  chk=d2937ba3ddba1bdc
//    ⇒ **两变体 chk 逐位相同**（probe 内置 MISMATCH 判定未触发）✓
//    ★ 且**命中相位与预测一致**：`loop` 段 −3.3%（正是"RAPP 读已与选择链重叠"的指纹），
//      而 `r0` 段几乎不动 ⇒ 不是整体漂移，是那一处延迟被盖住了 ✓
// ⑥ 交付声明：本发若更慢，榜单仍留 `#102821`（board 只留最好件）⇒ **零下行** ✓
// ======================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2, 提交 #102471 <https://duck.ac/submission/102471>
//     （复刻时的榜首，28.722 ms。**本提交写文件时** T 已由该账号的 #102527
//     <https://duck.ac/submission/102527> 推进到 28.4436 ms —— 他已把本账号
//     #102522 的 [W] 抄走；我方 #102522 = 28.2186 ms 仍是榜首，thr=28.1602 ms）
//     用途：**直接复制全文作为正文基底**。该文件正文与本账号自己的 #100289
//     （<https://duck.ac/submission/100289>，文件 problems/noip17f/work/n3f_f1.cpp）
//     **逐字节相同**，只有第 83 行 `#define NF_SIMPLECLS 0` → `1` 与第 86 行
//     `#define NF_PFD 8` → `4` 两处宏值不同；即对手把本账号的公开提交原样取用，
//     只改了 `NF_SIMPLECLS`（撤掉 SIMPLE1 位图、行类别全部由 RINF 标签给出）。
//     本轮按 RULES §3 引用其提交地址后，同样以其全文为基底（这是双方公开供应链的
//     正常用法，见 BRIEF §2.18.528）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #100289
//     <https://duck.ac/submission/100289>  文件 problems/noip17f/work/n3f_f1.cpp
//     用途：本提交正文的真实来源（= [1] 的正文）。其中 `kth_alive_del()` 融合、
//     惰性求值（RAPP 只存列位置引用）、`RINF[QX[i+4]]` 非依赖预取、SIMPLE1/SIMPLE2
//     行分类、文件级 target pragma 均为本账号前几轮提出（其自身引用见该提交文件头）。
// [3] duck.ac 用户 saffah_cc_v41_260924, 提交 #100076 <https://duck.ac/submission/100076>
//     用途：**直接复制**了 `kth_alive_del()`（本账号 #100289 已含，见 [2]）。
// ======================
// ===== 思路 =====
// 单变量刀 [HOIST2]：**同一根轴上的第二步** —— 把 c>=3 行的"位置计算"
// `small_remove(SMALLD+ro, ap, y)`（或真大行的 `kth_alive_del`）也提到列选择**之前**发。
// 现状：T = 27.779731 ms（对手 #102600），thr = 27.502934 ms `[0.99*T]`；
//   上一步 [HOIST]（#102808）刚把本账号最好从 27.776435 推到 **27.594727 ms（−0.654%）**
//   ⇒ 缺口从 0.98% 缩到 **0.33%**。
// ★ 轴的选择有本轮**新做的 phase 3 三面标定**背书（见 notes）：
//   gcc 9.3 的最内层循环 = 332 条指令 / 估 ~240 uop，而判题机只付 **223 周期/查询**
//   ⇒ **IPC ≈ 1.05**（发射宽度 4）⇒ **依赖链受限，不是 uop 受限** ⇒ 只有"缩短/重叠链"的刀才兑现。
//   本轮经验：加东西的刀全负、省 uop 的刀不兑现、而 [W]/[WLEN]/[HOIST] 三发全是延迟型且全为正。
// ★ 为什么这一步能重叠：`small_remove` 的地址只依赖 `ro`/`ap`/`y`（即上一刀已经提前读到的
//   描述符），**与 `pc` 无关**；但它要写 `u32 *R`（`SMALLD`），而列选择要写 `u64 *del`/
//   `u16 *bc`… ⇒ **编译器无法证明二者不别名，因此不会自动上移**，
//   于是这次随机访存（L2/L3）的延迟**整段暴露在关键路径上**。手工提前即可让它与选择链重叠。
// ★ 正确性注意（本轮实际踩到并修正）：判定条件里 **`t2 == 0` 就是"c>=3 的小行"**，
//   第一版误写成 `if (t2 && ...)` 把它排除了 ⇒ 在 8/12 组数据上报错（`val` 退化成 `(x-1)*m+0`）。
//   修正后 `nf2_verify.sh` 在 **12 组数据**上与 #102808 逐字节一致；阳性对照（`hopp+1`）
//   在 **11/12 组**上报失配 ⇒ 台架是活的。
// 本次为**单变量**提交（只把类 3 的位置计算提前到选择之前；其余一字未动）。
// ================
#include <emmintrin.h>
#pragma GCC optimize("O3","no-tree-slp-vectorize")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,sse4.1,ssse3")
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned u32;
typedef unsigned long long u64;
typedef long long i64;
#define NF_LAZY 1
// ===== nf3_engine.h  (engine template; wrapped into a namespace by nf3_gen.py) =====
// Base: problems/noip17f/work/hn_r20.cpp  (= current best #99566, 32.018 ms; its references:
// rival saffah_cc_v41_260924 #98371 / #99470 / #99533, and our own #99474).
// Variant knobs (set by the generator as -D macros around this text):
//   NF_LAZY      0/1 : do not compute the column value eagerly; store the column POSITION
//                      (a 20-bit reference) in the row's append slot and resolve the value
//                      only where it is actually needed (lazy construction / on-demand).
//   NF_SIMPLECLS 0/1 : drop the SIMPLE1 bitmap; every row class comes from the RINF tag
//                      (single 8-byte load, already software-prefetched) instead of a
//                      second random bitmap load.
//   NF_PFD          : software prefetch distance for RINF[QX[i+D]]  (0 = off)
//   NF_CAPP5       1 : enable the 40-bit compact column-append store (r20 declared CAPP5on
//                      but never assigned it, so it always used the 2.4 MB u64 array).
#ifndef NF_LAZY
#define NF_LAZY 0
#endif
#ifndef NF_SIMPLECLS
#define NF_SIMPLECLS 1
#endif
#ifndef NF_PFD
#define NF_PFD 4
#endif
#ifndef NF_CAPP5
#define NF_CAPP5 1
#endif
#ifndef NF_ARENA
#define NF_ARENA (144u << 20)
#endif

static const u8 *gip;
static u8 *gob;
static u32 g_n, g_m;              // for resolve()
#ifdef PROF
static unsigned long PT[16]; static int PTC;
static inline unsigned long rdt(){ unsigned a,d; __asm__ volatile("rdtsc":"=a"(a),"=d"(d)); return ((unsigned long)d<<32)|a; }
#define PTICK() PT[PTC++]=rdt()
#else
#define PTICK() ((void)0)
#endif

// ------------------------- fast input -------------------------
static const u64 MASKV[9] = {0ULL, 0xFFULL, 0xFFFFULL, 0xFFFFFFULL, 0xFFFFFFFFULL,
                             0xFFFFFFFFFFULL, 0xFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFULL,
                             0xFFFFFFFFFFFFFFFFULL};
static const u32 INV5[9] = {1u,        0xCCCCCCCDu, 0xC28F5C29u, 0x26E978D5u, 0x3AFB7E91u,
                            0x0BCBE61Du, 0x68C26139u, 0xAE8D46A5u, 0x22E90E21u};

static inline u32 rd() {
  for (;;) {
    u64 x;
    __builtin_memcpy(&x, gip, 8);
    u64 t = x ^ 0x3030303030303030ULL;
    u64 mm = ((t + 0x7676767676767676ULL) | t) & 0x8080808080808080ULL;
    u32 k = mm ? (u32)(__builtin_ctzll(mm) >> 3) : 8u;
    if (k == 0) { gip++; continue; }
    u64 d = t << ((8u - k) << 3);
    u64 c1 = (d * 10 + (d >> 8)) & 0x00FF00FF00FF00FFULL;
    u64 c2 = (c1 * 100 + (c1 >> 16)) & 0x0000FFFF0000FFFFULL;
    u64 c3 = (c2 * 10000 + (c2 >> 32));
    gip += k + 1;
    return (u32)c3;
  }
}

// ------------------------- fast output -------------------------
static const char D2[201] =
    "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
    "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
    "8081828384858687888990919293949596979899";

static u32 T4[10000];
static u64 POW10[20];
static u8  LB[65];
static u16 WI[2048];                  // [WLEN] WI[hi] = shift | (len << 8),  hi = v/1e8
static inline void writer_init() {
  for (u32 i = 0; i < 10000; i++) {
    u32 h = i / 100, l = i - h * 100;
    u8 *p = (u8 *)&T4[i];
    p[0] = (u8)D2[2*h]; p[1] = (u8)D2[2*h+1]; p[2] = (u8)D2[2*l]; p[3] = (u8)D2[2*l+1];
  }
  u64 p = 1; for (int i = 0; i < 20; i++) { POW10[i] = p; p *= 10; }
  for (u32 h = 1; h < 2048; h++) {                    // [WLEN]
    u32 d = 1; u64 t = 10; while (t <= h) { t *= 10; d++; }
    WI[h] = (u16)(((4u - d) << 3) | ((8u + d) << 8));
  }
  WI[0] = 0;
  for (int bl = 1; bl <= 64; bl++) {
    u64 lo = (bl == 1) ? 1ULL : (1ULL << (bl - 1));
    u32 d = 1; u64 t = 1; while (t * 10 <= lo) { t *= 10; d++; }
    LB[bl] = (u8)d;
  }
}
static inline u8 *wr_safe(u8 *o, u64 v) {
  u8 tmp[24];
  u32 i = 24;
  if (v < 10) { o[0] = (u8)('0' + v); o[1] = '\n'; return o + 2; }
  while (v >= 100) {
    u32 r = (u32)(v % 100);
    v /= 100;
    i -= 2;
    tmp[i] = D2[2 * r];
    tmp[i + 1] = D2[2 * r + 1];
  }
  if (v < 10) {
    tmp[--i] = (u8)('0' + v);
  } else {
    i -= 2;
    tmp[i] = D2[2 * v];
    tmp[i + 1] = D2[2 * v + 1];
  }
  u32 len = 24 - i;
  for (u32 w = 0; w < len; w++) o[w] = tmp[i + w];
  o[len] = '\n';
  return o + len + 1;
}
static inline u8 *wr(u8 *o, u64 v) {
  if (v < 10) { o[0] = (u8)('0' + v); o[1] = '\n'; return o + 2; }
  // ---- cut [W] (earlier round): no stack round-trip, leading 4-digit group is constant.
  // ---- cut [WLEN] (this round): ONE L1-resident table load replaces the serial
  //      lzcnt -> LB[bl] -> POW10[d0] -> cmp chain, and moves the leading-group lookup
  //      out of the 40 KB table (which does not fit L1D) into this 4 KiB one.
  u64 hv = v / 100000000ULL;
  if (hv - 1ULL >= 2047ULL) return wr_safe(o, v);     // v < 1e8 or v >= 2.048e11: rare
  u32 t = WI[(u32)hv];
  u32 len = t >> 8, lg = len - 8u;                    // lg = digits(hv) in [1,4]
  u32 lo8 = (u32)(v - hv * 100000000ULL);
  u32 a = lo8 / 10000, b = lo8 - a * 10000;
  u64 pa = ((u64)T4[a] << 32) | (u64)T4[(u32)hv];
  pa >>= ((u32)(t & 0xFFu));
  __builtin_memcpy(o, &pa, 8);
  __builtin_memcpy(o + len - 4, &T4[b], 4);
  o[len] = '\n';
  return o + len + 1;
}

// ------------------------- k-th alive -------------------------
static inline __m128i pf16(__m128i v) {
  v = _mm_add_epi16(v, _mm_slli_si128(v, 2));
  v = _mm_add_epi16(v, _mm_slli_si128(v, 4));
  v = _mm_add_epi16(v, _mm_slli_si128(v, 8));
  return v;
}
static inline __m128i gt16u(__m128i a, __m128i b) {
  const __m128i sg_ = _mm_set1_epi16((short)0x8000);
  return _mm_cmpgt_epi16(_mm_xor_si128(a, sg_), _mm_xor_si128(b, sg_));
}
static inline u32 sel8(const u16 *p, u32 rem, u32 *sub) {
  __m128i inc = pf16(_mm_loadu_si128((const __m128i *)p));
  u32 msk = (u32)_mm_movemask_epi8(gt16u(inc, _mm_set1_epi16((short)(rem - 1))));
  u32 j = (u32)__builtin_ctz(msk) >> 1;
  u16 buf[8];
  _mm_storeu_si128((__m128i *)buf, _mm_slli_si128(inc, 2));
  *sub = (u32)buf[j];
  return j;
}
static inline u32 sel8w(const u8 *pw, u32 rem, u32 *sub) {
  __m128i b8 = _mm_loadl_epi64((const __m128i *)pw);
  __m128i a = _mm_sub_epi16(_mm_set1_epi16(64), _mm_unpacklo_epi8(b8, _mm_setzero_si128()));
  __m128i inc = pf16(a);
  u32 msk = (u32)_mm_movemask_epi8(gt16u(inc, _mm_set1_epi16((short)(rem - 1))));
  u32 j = (u32)__builtin_ctz(msk) >> 1;
  u16 buf[8];
  _mm_storeu_si128((__m128i *)buf, _mm_slli_si128(inc, 2));
  *sub = (u32)buf[j];
  return j;
}
static inline u32 kth_alive(const u64 *del, const u8 *wc, const u16 *bc, const u16 *gs, const u16 *sg, u32 k) {
  u32 rem = k, s = 0;
  while (rem > (u32)sg[s]) { rem -= sg[s]; s++; }
  u32 sub;
  u32 jg = sel8(gs + (s << 3), rem, &sub); rem -= sub;
  u32 g = (s << 3) + jg;
  u32 jb = sel8(bc + (g << 3), rem, &sub); rem -= sub;
  u32 b = (g << 3) + jb;
  u32 sub2;
  u32 wi = sel8w(wc + (b << 3), rem, &sub2); rem -= sub2;
  u32 base = (b << 9) + (wi << 6);
  u64 m = ~del[(b << 3) + wi];
  u64 r; __asm__("pdep %2, %1, %0" : "=r"(r) : "r"(1ULL << (rem - 1)), "r"(m));
  return base + (u32)__builtin_ctzll(r) + 1;
}
static inline void big_del(u64 *del, u8 *wc, u16 *bc, u16 *gs, u16 *sg, u32 p) {
  u32 w = p >> 6;
  u32 b = w >> 3, g = b >> 3, s = g >> 3;
  del[w] |= 1ULL << (p & 63);
  wc[w]++; bc[b]--; gs[g]--; sg[s]--;
}
// ---- [RIVAL-FUSED] kth_alive + big_del in ONE function -------------------------------
// Copied from duck.ac user saffah_cc_v41_260924, submission #100076 (their current rank-1,
// 30.191 ms), which gained -5.7% over their previous generation (#99562 -> #100076) with
// this single change.  Rationale (their comment, condensed): the deletion's (word, block,
// group, super) indices are EXACTLY the ones the select already produced, so big_del's four
// SERIAL shifts (w=p>>6, b=w>>3, g=b>>3, s=g>>3) are re-derivations of values already in
// registers -- and they sat on the critical path of a chain that runs once per query.
static inline u32 kth_alive_del(u64 *del, u8 *wc, u16 *bc, u16 *gs, u16 *sg, u32 k) {
  u32 rem = k, s = 0;
  while (rem > (u32)sg[s]) { rem -= sg[s]; s++; }
  u32 sub;
  u32 jg = sel8(gs + (s << 3), rem, &sub); rem -= sub;
  u32 g = (s << 3) + jg;
  u32 jb = sel8(bc + (g << 3), rem, &sub); rem -= sub;
  u32 b = (g << 3) + jb;
  u32 sub2;
  u32 wi = sel8w(wc + (b << 3), rem, &sub2); rem -= sub2;
  u32 w = (b << 3) + wi;
  u64 m = ~del[w];
  u64 r; __asm__("pdep %2, %1, %0" : "=r"(r) : "r"(1ULL << (rem - 1)), "r"(m));
  u32 bit = (u32)__builtin_ctzll(r);
  del[w] |= 1ULL << bit;
  wc[w]++; bc[b]--; gs[g]--; sg[s]--;
  return ((b << 9) + (wi << 6)) + bit + 1;
}
static inline unsigned long ka_need(u32 V) {
  u32 nwords = (V + 63) >> 6;
  u32 nblk = (nwords + 7) >> 3;
  u32 ngrp = (nblk + 7) >> 3;
  u32 nsup = (ngrp + 7) >> 3;
  u32 nbp = ngrp << 3, ngp = nsup << 3;
  unsigned long need = ((unsigned long)nwords << 3) + nwords + 1;
  need = (need + 1) & ~1UL; need += (((unsigned long)nbp) << 1) + 2;
  need = (need + 1) & ~1UL; need += (((unsigned long)ngp) << 1) + 2;
  need = (need + 1) & ~1UL; need += (((unsigned long)nsup) << 1) + 2;
  return (need + 63) & ~(unsigned long)63;
}
static inline unsigned long big_init(u8 *mem, u32 V, u64 **pdel, u8 **pwc,
                                     u16 **pbc, u16 **pgs, u16 **psg) {
  u32 nwords = (V + 63) >> 6;
  u32 nblk = (nwords + 7) >> 3;
  u32 ngrp = (nblk + 7) >> 3;
  u32 nsup = (ngrp + 7) >> 3;
  u32 nbp = ngrp << 3, ngp = nsup << 3;
  unsigned long o1 = (((unsigned long)nwords << 3) + 1) & ~1UL;
  unsigned long o2 = (o1 + nwords + 1) & ~1UL;
  unsigned long o3 = (o2 + (((unsigned long)nbp) << 1) + 1) & ~1UL;
  unsigned long o4 = (o3 + (((unsigned long)ngp) << 1) + 1) & ~1UL;
  u64 *del = (u64 *)mem;
  u8  *wc  = (u8 *)(mem + o1);
  u16 *bc  = (u16 *)(mem + o2);
  u16 *gs  = (u16 *)(mem + o3);
  u16 *sg  = (u16 *)(mem + o4);
  for (u32 i = 0; i < nwords; i++) { del[i] = 0; wc[i] = 0; }
  u32 hi = V & 63;
  if (hi) { del[nwords - 1] = ~0ULL << hi; wc[nwords - 1] = (u8)(64 - hi); }
  for (u32 i = 0; i < nbp; i++) bc[i] = 0;
  for (u32 i = 0; i < ngp; i++) gs[i] = 0;
  for (u32 i = 0; i < nsup; i++) sg[i] = 0;
  for (u32 i = 0; i < nwords; i++) bc[i >> 3] += (u16)(64u - (u32)wc[i]);
  for (u32 i = 0; i < nblk; i++)  gs[i >> 3] += bc[i];
  for (u32 i = 0; i < ngrp; i++)  sg[i >> 3] += gs[i];
  *pdel = del; *pwc = wc; *pbc = bc; *pgs = gs; *psg = sg;
  return ka_need(V);
}

static inline u32 small_remove(u32 *R, u32 d, u32 k) {
  u32 lo = 0, hi = d;
  while (lo < hi) {
    u32 mid = (lo + hi + 1) >> 1;
    if (R[mid - 1] - mid < k) lo = mid; else hi = mid - 1;
  }
  u32 p = k + lo;
  if (lo < d) {
    u32 *s = R + d, *e = R + lo;
    while (s > e) { *s = s[-1]; s--; }
  }
  R[lo] = p;
  return p;
}

// ------------------------- globals -------------------------
#define PN 300005
static u32 QX[PN], QY[PN];
struct RINF_T { u32 offb; u32 appn; };
static RINF_T RINF[PN];
static u64 SIMPLE1[(PN + 63) / 64];
static u32 BIGD[8192][8];
#if NF_LAZY
static u32 RAPP[PN];                  // NF_LAZY: stores a column POSITION reference (<= n+q)
#else
static u64 RAPP[PN];                  // stores the column value
#endif
static u32 SMALLD[PN];
static u64 CAPP[PN];
static u8  CAPP5[PN * 5 + 8];
static int CAPP5on;

#ifndef NF_ARENA
#define NF_ARENA (144u << 20)
#endif
#define ARENASZ ((unsigned long)NF_ARENA)
static u8 ARENA[NF_ARENA];

static u64 *CDEL; static u8 *CWC; static u16 *CBC; static u16 *CGS; static u16 *CSG;

#if NF_LAZY
// Resolve a column POSITION p to the value living there.  Called only on the rare paths
// where the answer really is a column-appended value (p > n): deferred construction.
static inline u64 resolve(u32 p) {
  if (p <= g_n) return (u64)p * g_m;
  u32 jj = p - g_n - 1;
  if (CAPP5on) { u32 lo_; __builtin_memcpy(&lo_, CAPP5 + (size_t)jj * 5, 4);
                 return (u64)lo_ | ((u64)CAPP5[(size_t)jj * 5 + 4] << 32); }
  return CAPP[jj];
}
#endif

// returns output length; PT[0..3] = phase ticks when PROF
static unsigned long nf_solve(u8 *out) {
#ifdef PROF
  PTC = 0;
#endif
  writer_init();
  PTICK();
  u32 n = rd(), m = rd(), q = rd();
  g_n = n; g_m = m;
#if NF_CAPP5
  CAPP5on = ((u64)n * (u64)m < (1ULL << 40));
#else
  CAPP5on = 0;
#endif
  u32 mm1 = m - 1;
  // ---- phase 1 ----
  for (u32 i = 0; i < q; i++) {
    u32 x = rd(), y = rd();
    QX[i] = x; QY[i] = y;
    if (y < m) SMALLD[x]++;
  }
  PTICK();
  // ---- phase 2 ----
  u32 off = 0;
  u32 nbig = 0;
  unsigned long asz = 0;
  for (u32 r = 1; r <= n; r++) {
    u32 c = SMALLD[r];
    if (!c) continue;
#if NF_SIMPLECLS
    if (c == 1) { RINF[r].offb = (0x1FFEu << 19); RINF[r].appn = 0; continue; }
#else
    if (c == 1) { SIMPLE1[r >> 6] |= 1ULL << (r & 63); continue; }
#endif
    if (c == 2) { RINF[r].offb = (0x1FFFu << 19); RINF[r].appn = 0; continue; }
    u32 tag = 0;
    u64 V = (u64)mm1 + c;
    i64 cs = (i64)c * ((i64)(c >> 3) + 30);
    i64 cb = (i64)((V >> 6) + 1) * 2 + (i64)c * 55;
    if (cb < cs && nbig < 8190) {
      unsigned long need = ka_need((u32)V);
      if (asz + need <= ARENASZ - (1u << 20)) {
        u64 *pdel; u8 *pwc; u16 *pbc; u16 *pgs; u16 *psg;
        big_init(ARENA + asz, (u32)V, &pdel, &pwc, &pbc, &pgs, &psg);
        u32 *D = BIGD[nbig];
        D[0] = (u32)((u8 *)pdel - ARENA); D[1] = (u32)((u8 *)pwc - ARENA);
        D[2] = (u32)((u8 *)pbc - ARENA);  D[3] = (u32)((u8 *)pgs - ARENA);
        D[4] = (u32)((u8 *)psg - ARENA);
        asz += need;
        tag = ++nbig;
      }
    }
    RINF[r].offb = (off & 0x7FFFFu) | (tag << 19);
    RINF[r].appn = 0;
    off += c;
  }
  PTICK();
  // ---- column ----
  {
    u64 *pdel; u8 *pwc; u16 *pbc; u16 *pgs; u16 *psg;
    unsigned long need = big_init(ARENA + asz, n + q, &pdel, &pwc, &pbc, &pgs, &psg);
    asz += need;
    CDEL = pdel; CWC = pwc; CBC = pbc; CGS = pgs; CSG = psg;
  }
  PTICK();
  // ---- phase 3 ----
  u32 cappn = 0;
  u8 *o = out;
  for (u32 i = 0; i < q; i++) {
    u32 x = QX[i], y = QY[i];
#if NF_PFD > 0
    if (i + NF_PFD < q) __builtin_prefetch(&RINF[QX[i + NF_PFD]], 0, 3);
#endif
    // [HOIST] row-descriptor load, issued before the column select (see header)
    u32 hoffb = 0, happn = 0;
    if (y < m) { hoffb = RINF[x].offb; happn = RINF[x].appn; }
    // [HOIST2] the c>=3 row path's position computation is also pc-independent: start it now so
    // its SMALLD/arena latency overlaps the select chain instead of following it.
    u32 ho3 = 0, hopp = 0;
    if (y < m) {
      u32 t2 = hoffb >> 19;
      if (t2 != 0x1FFEu && t2 != 0x1FFFu) {   // t2 == 0 is the c>=3 SMALL row
        u32 ro2 = hoffb & 0x7FFFFu, ap2 = happn;
        if (t2) {
          const u32 *D = BIGD[t2 - 1];
          u64 *pdel = (u64 *)(ARENA + D[0]); u8 *pwc = (u8 *)(ARENA + D[1]);
          u16 *pbc = (u16 *)(ARENA + D[2]); u16 *pgs = (u16 *)(ARENA + D[3]);
          u16 *psg = (u16 *)(ARENA + D[4]);
          hopp = kth_alive_del(pdel, pwc, pbc, pgs, psg, y);
        } else {
          hopp = small_remove(SMALLD + ro2, ap2, y);
        }
        ho3 = 1;
      }
    }
    // [HOIST3] same axis, third step: `pp` and the lazy RAPP read + `resolve` are pc-independent
    // as well -- their address only needs the [HOIST]/[HOIST2] descriptors (ro/ap/hopp), none of
    // which depend on the column select.  Issuing them before the select lets that latency overlap
    // the select chain instead of following it.  Read-before-write within the iteration is
    // preserved (the RAPP store still stays after the select), so this is a pure reorder: the
    // expressions below are byte-for-byte the ones the big-row path used to evaluate later.
    u32 hpp = 0; u64 hrv = 0;
    if (y < m && ho3) {
      hpp = hopp;
      hrv = (hpp <= mm1) ? ((u64)(x - 1) * m + hpp)
                         : resolve(RAPP[(hoffb & 0x7FFFFu) + (hpp - m)]);
    }
    u32 pc = kth_alive_del(CDEL, CWC, CBC, CGS, CSG, x);
#if !NF_LAZY
    u64 cval;
    if (pc <= n) cval = (u64)pc * m;
    else {
      u32 jj = pc - n - 1;
      if (CAPP5on) { u32 lo_; __builtin_memcpy(&lo_, CAPP5 + (size_t)jj * 5, 4);
                     cval = (u64)lo_ | ((u64)CAPP5[(size_t)jj * 5 + 4] << 32); }
      else cval = CAPP[jj];
    }
#endif
    u64 val;
    if (y < m) {
      u32 r = x;
#if !NF_SIMPLECLS
      if ((SIMPLE1[r >> 6] >> (r & 63)) & 1ULL) {
        val = (u64)(r - 1) * m + y;
      } else {
#endif
      u32 offb = hoffb;                 // [HOIST] loaded above, in parallel with the select
      u32 t = offb >> 19;
      u32 ro = offb & 0x7FFFFu;
      u32 ap = happn;
      u32 pp;
#if NF_SIMPLECLS
      if (t == 0x1FFEu) {
        val = (u64)(r - 1) * m + y;
      } else
#endif
      if (t == 0x1FFFu) {
        u32 p0 = offb & 0x7FFFFu;
        if (!p0) {
          pp = y;
          RINF[r].offb = (0x1FFFu << 19) | y;
          RINF[r].appn = pc + 1;
          val = (u64)(r - 1) * m + pp;
        } else {
          pp = y + (y >= p0 ? 1u : 0u);
          if (pp <= mm1) val = (u64)(r - 1) * m + pp;
          else {
            u32 pcc = RINF[r].appn - 1;
#if NF_LAZY
            val = resolve(pcc);
#else
            if (pcc <= n) val = (u64)pcc * m;
            else { u32 jj = pcc - n - 1;
              if (CAPP5on) { u32 lo_; __builtin_memcpy(&lo_, CAPP5 + (size_t)jj * 5, 4);
                             val = (u64)lo_ | ((u64)CAPP5[(size_t)jj * 5 + 4] << 32); }
              else val = CAPP[jj];
            }
#endif
          }
        }
      } else {
        (void)ro; (void)ap;
        pp = hpp;                         // [HOIST3] computed above, overlapped with the select
#if NF_LAZY
        u64 rv = hrv;                     // [HOIST3] likewise (pure reorder; same expression)
        RAPP[ro + ap] = pc;                    // store the POSITION reference, not the value
        val = rv;
#else
        val = (pp <= mm1) ? ((u64)(r - 1) * m + pp) : RAPP[ro + (pp - m)];
        RAPP[ro + ap] = cval;
#endif
        RINF[r].appn = ap + 1;
      }
#if !NF_SIMPLECLS
      }
#endif
    } else {
#if NF_LAZY
      val = resolve(pc);
#else
      val = cval;
#endif
    }
    { size_t o_ = (size_t)cappn * 5;
      if (CAPP5on) { u32 lo_ = (u32)val; __builtin_memcpy(CAPP5 + o_, &lo_, 4); CAPP5[o_ + 4] = (u8)(val >> 32); }
      else CAPP[cappn] = val; }
    cappn++;
    o = (i + 1 == q) ? wr_safe(o, val) : wr(o, val);
  }
  PTICK();
  return (unsigned long)(o - out);
}

static unsigned long nf_run(const u8 *in, u8 *out) { gip = in; return nf_solve(out); }

struct DUCKDI{unsigned long abi;const char*sp;unsigned long sn;char*op;unsigned long ol,os;char*ep;unsigned long el,es;const char*IB;unsigned long IBl;char*OB;unsigned long OBl;unsigned long tsc;}__attribute__((packed));
extern "C" void __libc_start_main(void*m,int argc,char**argv){
 unsigned long*p=(unsigned long*)(argv+argc+1);while(*p)p++;p++;
 DUCKDI*d=0;for(;p[0];p+=2)if(p[0]==0x6b637564UL){d=(DUCKDI*)p[1];break;}
 gip=(const u8*)d->sp; gob=(u8*)d->op;
 unsigned long olen = nf_solve(gob);
 gob=(u8*)d->op+olen;
 d->os=olen;
 __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
 for(;;);
}
int main(){return 0;}

评测结果