代码

#include "router.h"

#include <stdint.h>
#include <arpa/inet.h>

#include <algorithm>

static inline bool in_entry_range(const RoutingTableEntry &e, uint32_t addr) {
	return (uint64_t) (addr ^ e.addr) >> (32 - e.len) == 0;
}

const int MAXN = 900000;

static uint32_t left[MAXN * 2];
static uint32_t nexthops[MAXN * 2];
static int n_intervals;

static inline void append(uint32_t l, uint32_t nexthop) {
	if (left[n_intervals - 1] == l) {
		nexthops[n_intervals - 1] = nexthop;
	} else if (left[n_intervals - 1] < l) {
		left[n_intervals] = l;
		nexthops[n_intervals] = nexthop;
		++n_intervals;
	}
}

void init(int n, int q, const RoutingTableEntry *a) {
	RoutingTableEntry stack[34];
	int top = 0;
	
	stack[0].nexthop = -1u;
	
	n_intervals = 1;
	left[0] = 0;
	nexthops[0] = 0;
	
	for (int i = 0; i < n; i++) {
		RoutingTableEntry tmp = a[i];
		uint32_t addr = tmp.addr = htonl(tmp.addr);
		while (top && !in_entry_range(stack[top], addr)) {
			append(stack[top].addr + (1ull << (32 - stack[top].len)), stack[top - 1].nexthop);
			--top;
		}
		stack[++top] = tmp;
		append(tmp.addr, tmp.nexthop);
	}
	
	while (top) {
		append(stack[top].addr + (1ull << (32 - stack[top].len)), stack[top - 1].nexthop);
		--top;
	}
}

unsigned query(unsigned addr) {
	addr = htonl(addr);
	
	if (addr == -1u) {
		return nexthops[n_intervals - 1];
	} else {
		int id = std::lower_bound(left, left + n_intervals, addr + 1) - left - 1;
		return nexthops[id];
	}
}

评测结果