代码

#ifndef DUCK_FASTIO_H
#define DUCK_FASTIO_H

typedef unsigned long duck_u64;
typedef long duck_i64;

typedef struct {
    duck_u64 abi_version;
    const char *stdin_ptr;
    duck_u64 stdin_size;
    char *stdout_ptr;
    duck_u64 stdout_limit;
    duck_u64 stdout_size;
    char *stderr_ptr;
    duck_u64 stderr_limit;
    duck_u64 stderr_size;
    const char *ib_ptr;
    duck_u64 ib_limit;
    char *ob_ptr;
    duck_u64 ob_limit;
    duck_u64 tsc_frequency;
} __attribute__((packed)) DuckInfo;

static __attribute__((always_inline)) inline DuckInfo *duck_info(long argc, char **argv) {
    char **p = argv + argc + 1;
    while (*p) ++p;
    duck_u64 *aux = (duck_u64 *)(p + 1);
    while (aux[0]) {
        if (aux[0] == 0x6b637564UL) return (DuckInfo *)aux[1];
        aux += 2;
    }
    return (DuckInfo *)0;
}

static __attribute__((always_inline)) inline duck_u64 duck_read_u64(const char **cursor) {
    const char *p = *cursor;
    while ((unsigned char)(*p - '0') > 9) ++p;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return value;
}

static __attribute__((always_inline)) inline duck_i64 duck_read_i64(const char **cursor) {
    const char *p = *cursor;
    while (*p != '-' && (unsigned char)(*p - '0') > 9) ++p;
    int negative = *p == '-';
    p += negative;
    duck_u64 value = 0;
    do {
        value = value * 10 + (unsigned char)(*p - '0');
        ++p;
    } while ((unsigned char)(*p - '0') <= 9);
    *cursor = p;
    return negative ? -(duck_i64)value : (duck_i64)value;
}

static __attribute__((always_inline)) inline char *duck_write_u64(char *out, duck_u64 value) {
    char tmp[24];
    unsigned n = 0;
    do {
        tmp[n++] = (char)('0' + value % 10);
        value /= 10;
    } while (value);
    do *out++ = tmp[--n]; while (n);
    return out;
}

static __attribute__((always_inline)) inline char *duck_write_i64(char *out, duck_i64 value) {
    if (value < 0) {
        *out++ = '-';
        return duck_write_u64(out, (duck_u64)(-value));
    }
    return duck_write_u64(out, (duck_u64)value);
}

static __attribute__((always_inline, noreturn)) inline void duck_exit(void) {
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall" ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

#endif


typedef unsigned int u32;
typedef unsigned long u64;

enum { MAXN = 300000, MAXQ = 300000, MAXNODE = MAXQ + 8 };

static u32 query_x[MAXQ], query_y[MAXQ];
static u32 row_root[MAXN + 1], row_count[MAXN + 1];
static u32 row_offset[MAXN + 1], row_used[MAXN + 1];
static u64 row_extra[MAXQ], column_extra[MAXQ];
static u32 column_alive[MAXN + MAXQ + 8];
static u32 column_limit, column_step;

static u32 left_child[MAXNODE], right_child[MAXNODE];
static u32 node_key[MAXNODE], node_priority[MAXNODE], node_size[MAXNODE];
static u32 nodes_used;
static u32 random_state = 0x243f6a88u;

static __attribute__((always_inline)) inline u32 random_u32(void) {
    u32 x = random_state;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    random_state = x;
    return x;
}

static __attribute__((always_inline)) inline void refresh(u32 root) {
    node_size[root] = node_size[left_child[root]] + node_size[right_child[root]] + 1;
}

/* Return and erase the kth positive integer not already stored in the tree. */
static __attribute__((always_inline)) inline u32 take_kth(u32 *root_ptr, u32 k) {
    u32 root = *root_ptr;
    u32 below = 0;
    u32 path[96];
    unsigned char direction[96];
    unsigned depth = 0;
    while (root) {
        path[depth] = root;
        u32 less = below + node_size[left_child[root]];
        u32 missing_before = node_key[root] - 1 - less;
        if (k <= missing_before) {
            direction[depth++] = 0;
            root = left_child[root];
        } else {
            direction[depth++] = 1;
            below = less + 1;
            root = right_child[root];
        }
    }
    u32 position = k + below;
    u32 fresh = ++nodes_used;
    left_child[fresh] = right_child[fresh] = 0;
    node_key[fresh] = position;
    node_priority[fresh] = random_u32();
    node_size[fresh] = 1;

    /* Reuse the search path to insert and restore the treap heap property. */
    u32 subtree = fresh;
    while (depth) {
        --depth;
        u32 parent = path[depth];
        if (!direction[depth]) {
            left_child[parent] = subtree;
            if (node_priority[subtree] < node_priority[parent]) {
                left_child[parent] = right_child[subtree];
                right_child[subtree] = parent;
                refresh(parent);
                refresh(subtree);
            } else {
                refresh(parent);
                subtree = parent;
            }
        } else {
            right_child[parent] = subtree;
            if (node_priority[subtree] < node_priority[parent]) {
                right_child[parent] = left_child[subtree];
                left_child[subtree] = parent;
                refresh(parent);
                refresh(subtree);
            } else {
                refresh(parent);
                subtree = parent;
            }
        }
    }
    *root_ptr = subtree;
    return position;
}

static __attribute__((always_inline)) inline u32 take_column(u32 k) {
    u32 position = 0;
    for (u32 step = column_step; step; step >>= 1) {
        u32 next = position + step;
        if (next <= column_limit && column_alive[next] < k) {
            position = next;
            k -= column_alive[next];
        }
    }
    ++position;
    for (u32 i = position; i <= column_limit; i += i & -i)
        --column_alive[i];
    return position;
}

__attribute__((noreturn))
void __libc_start_main(void *unused, long argc, char **argv) {
    (void)unused;
    DuckInfo *info = duck_info(argc, argv);
    const char *input = info->stdin_ptr;
    char *out = info->stdout_ptr;
    u32 n = (u32)duck_read_u64(&input);
    u32 m = (u32)duck_read_u64(&input);
    u32 q = (u32)duck_read_u64(&input);

    for (u32 i = 0; i < q; ++i) {
        u32 x = (u32)duck_read_u64(&input);
        u32 y = (u32)duck_read_u64(&input);
        query_x[i] = x;
        query_y[i] = y;
        row_count[x] += y != m;
    }

    u32 total = 0;
    for (u32 x = 1; x <= n; ++x) {
        row_offset[x] = total;
        total += row_count[x];
    }

    column_limit = n + q;
    column_step = 1;
    while ((column_step << 1) <= column_limit) column_step <<= 1;
    for (u32 i = 1; i <= column_limit; ++i) column_alive[i] = i & -i;

    for (u32 event = 0; event < q; ++event) {
        u32 x = query_x[event];
        u32 y = query_y[event];
        u64 answer;

        if (y == m) {
            u32 position = take_column(x);
            answer = position <= n ? (u64)position * m
                                   : column_extra[position - n - 1];
            column_extra[event] = answer;
        } else {
            u32 position = take_kth(&row_root[x], y);
            answer = position < m ? (u64)(x - 1) * m + position
                                  : row_extra[row_offset[x] + position - m];

            position = take_column(x);
            u64 moved = position <= n ? (u64)position * m
                                      : column_extra[position - n - 1];
            row_extra[row_offset[x] + row_used[x]++] = moved;
            column_extra[event] = answer;
        }

        out = duck_write_u64(out, answer);
        *out++ = '\n';
    }

    info->stdout_size = (u64)(out - info->stdout_ptr);
    duck_exit();
}

int main(void) {}

评测结果