省时之题解

能做到的最省时又最省空间的方案：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

// ===== 小缓冲快读（256KB，省 768KB，速度几乎不变）=====
static char ibuf[1 << 18];
static int ilen = 0, ipos = 0;

static inline int gc() {
    if (ipos == ilen) {
        ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin);
        ipos = 0;
        if (ilen == 0) return -1;
    }
    return ibuf[ipos++];
}

#define READINT(x) do { \
    int c = gc(); \
    while (c < '0' || c > '9') c = gc(); \
    x = 0; \
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); } \
} while(0)

#define SHIFT 20
#define MASK  ((1 << SHIFT) - 1)

signed main(void) {
    int N, M, T;
    READINT(N); READINT(M); READINT(T);

    // ===== VLA 按需分配 =====
    long long orders[M > 0 ? M : 1];
    int last[N + 1];
    int prio[N + 1];
    unsigned long long cachedBits[(N >> 6) + 2];

    // 合并 memset：last 和 prio 一起清
    memset(last, 0, sizeof(int) * (N + 1));
    memset(prio, 0, sizeof(int) * (N + 1));
    memset(cachedBits, 0, sizeof(unsigned long long) * ((N >> 6) + 2));

    // 读入并打包
    for (int i = 0; i < M; i++) {
        int ts, id;
        READINT(ts);
        READINT(id);
        orders[i] = ((long long)ts << SHIFT) | id;
    }

    sort(orders, orders + M);

    // 按 (ts, id) 分组
    int i = 0;
    while (i < M) {
        long long key = orders[i];
        int ts = (int)(key >> SHIFT);
        int id = (int)(key & MASK);
        int cnt = 0;
        while (i < M && orders[i] == key) {
            cnt++;
            i++;
        }

        int gap = ts - last[id] - 1;
        if (gap > 0) {
            prio[id] -= gap;
            if (prio[id] < 0) prio[id] = 0;
        }
        if (prio[id] <= 3) {
            int word = id >> 6;
            cachedBits[word] &= ~(1ULL << (id & 63));
        }
        prio[id] += 2 * cnt;
        if (prio[id] > 5) {
            int word = id >> 6;
            cachedBits[word] |= 1ULL << (id & 63);
        }
        last[id] = ts;
    }

    // 尾巴处理 + 统计合并
    int ans = 0;
    for (int id = 1; id <= N; id++) {
        int gap = T - last[id];
        if (gap > 0) {
            prio[id] -= gap;
            if (prio[id] < 0) prio[id] = 0;
        }
        int word = id >> 6;
        if (prio[id] <= 3) {
            cachedBits[word] &= ~(1ULL << (id & 63));
        }
        if ((cachedBits[word] >> (id & 63)) & 1) ans++;
    }

    printf("%d\n", ans);
    return 0;
}