Submission #72998191

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>

int cmp(const void* x, const void* y) {
	int a = *(const int*)x, b = *(const int*)y;
	return (a > b) - (a < b);
}

int zac;
int zal[114514 * 3];

int zaq(int query) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zal[m] == query) return m;
		else if (zal[m] < query) l = m + 1;
		else r = m - 1;
	}
	printf("ERROR: %d not found!\n", query);
	exit(72);
}

/* 範囲1をadd、点get */

#define KI_MAX (1 << 19) /* 524288 */

struct ki_node {
	int delta;
	int children[2];
};

#define POOL_MAX 5200000

int pool_count;
struct ki_node pool[POOL_MAX];

int create_new_node(int from) {
	if (pool_count >= POOL_MAX) {
		puts("MLE!");
		exit(42);
	}
	if (from >= 0) {
		pool[pool_count] = pool[from];
	} else {
		pool[pool_count].delta = 0;
		pool[pool_count].children[0] = -1;
		pool[pool_count].children[1] = -1;
	}
	return pool_count++;
}

int ki_add_i(int node, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		int new_node = create_new_node(node);
		pool[new_node].delta++;
		return new_node;
	} else if (se <= qs || qe <= ss) { /* 完全に外れている */
		return node;
	} else {
		int sm = ss + (se - ss) / 2;
		int new_node = create_new_node(node);
		pool[new_node].children[0] = ki_add_i(pool[new_node].children[0], ss, sm, qs, qe);
		pool[new_node].children[1] = ki_add_i(pool[new_node].children[1], sm, se, qs, qe);
		return new_node;
	}
}

int ki_add(int node, int qs, int qe) {
	return ki_add_i(node, 0, KI_MAX, qs, qe);
}

int ki_get_i(int node, int ss, int se, int q) {
	if (node < 0) { /* このノードとその子孫は全て0 */
		return 0;
	} else if (ss == q && se == q + 1) { /* セグメントがクエリに完全に含まれる (葉) */
		return pool[node].delta;
	} else if (q < ss || se <= q) { /* 完全に外れている */
		return 0;
	} else {
		int sm = ss + (se - ss) / 2;
		return pool[node].delta +
			ki_get_i(pool[node].children[0], ss, sm, q) +
			ki_get_i(pool[node].children[1], sm, se, q);
	}
}

int ki_get(int node, int q) {
	return ki_get_i(node, 0, KI_MAX, q);
}

int n, m, k;
int a[114514], b[114514];
int p[114514], q[114514], r[114514];

int data[114514];

int main(void) {
	int i;
	if (scanf("%d%d%d", &n, &m, &k) != 3) return 1;
	for (i = 1; i <= n; i++) {
		if (scanf("%d%d", &a[i], &b[i]) != 2) return 1;
		zal[i * 2 - 2] = a[i];
		zal[i * 2 - 1] = b[i];
	}
	for (i = 0; i < m; i++) {
		if (scanf("%d%d%d", &p[i], &q[i], &r[i]) != 3) return 1;
		zal[n * 2 + i] = p[i];
	}
	qsort(zal, n * 2 + m, sizeof(*zal), cmp);
	for (i = 1, zac = 1; i < n * 2 + m; i++) {
		if (zal[zac - 1] != zal[i]) zal[zac++] = zal[i];
	}
	data[0] = -1;
	for (i = 1; i <= n; i++) {
		data[i] = ki_add(data[i - 1], zaq(a[i]), zaq(b[i]) + 1);
	}
	for (i = 0; i < m; i++) {
		int id = zaq(p[i]);
		printf("%d\n", ki_get(data[r[i]], id) - ki_get(data[q[i] - 1], id));
	}
	return 0;
}

Submission Info

Judge Result