Submission #73971861

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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[212345 * 2];
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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#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[212345 * 2];

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);
}

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

int ki[KI_MAX * 2 - 1];
char ki_all[KI_MAX * 2 - 1];

/* 黒にする */

int ki_set_i(int idx, int ss, int se, int qs, int qe) {
	if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		ki_all[idx] = 1;
	} else if (qe <= ss || se <= qs) { /* 完全に外れている */
		/* 何もしない */
	} else {
		int sm = ss + (se - ss) / 2;
		ki[idx] = ki_set_i(idx * 2 + 1, ss, sm, qs, qe) +
			ki_set_i(idx * 2 + 2, sm, se, qs, qe);
	}
	return ki_all[idx] ? zal[se] - zal[ss] : ki[idx];
}

void ki_set(int qs, int qe) {
	ki_set_i(0, 0, KI_MAX, qs, qe);
}

/* 黒く塗られているマスの個数を求める */

int ki_get_i(int idx, int ss, int se, int qs, int qe) {
	if (qe <= ss || se <= qs) { /* 完全に外れている */
		return 0;
	} else if (ki_all[idx]) { /* 範囲内全マスが黒く塗られている */
		int l = ss <= qs ? qs : ss;
		int r = se <= qe ? se : qe;
		return zal[r] - zal[l];
	} else if (qs <= ss && se <= qe) { /* セグメントがクエリに完全に含まれる */
		return ki[idx];
	} else {
		int sm = ss + (se - ss) / 2;
		return ki_get_i(idx * 2 + 1, ss, sm, qs, qe) +
			ki_get_i(idx * 2 + 2, sm, se, qs, qe);
	}
}

int ki_get(int qs, int qe) {
	return ki_get_i(0, 0, KI_MAX, qs, qe);
}

int N, Q;
int L[212345], R[212345];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &L[i], &R[i]) != 2) return 1;
		zal[i * 2] = L[i];
		zal[i * 2 + 1] = R[i] + 1;
	}
	zal[Q * 2] = N + 1;
	qsort(zal, Q * 2 + 1, sizeof(*zal), cmp);
	for (i = 1, zac = 1; i < Q * 2 + 1; i++) {
		if (zal[zac - 1] != zal[i]) zal[zac++] = zal[i];
	}
	for (i = 0; i < Q; i++) {
		ki_set(zaq(L[i]), zaq(R[i] + 1));
		printf("%d\n", N - ki_get(0, zac - 1));
	}
	return 0;
}

Submission Info

Compile Error

In function ‘ki_set_i’,
    inlined from ‘ki_set’ at Main.c:45:2:
Main.c:41:33: warning: array subscript 524288 is above array bounds of ‘int[424690]’ [-Warray-bounds=]
   41 |         return ki_all[idx] ? zal[se] - zal[ss] : ki[idx];
      |                              ~~~^~~~
Main.c: In function ‘ki_set’:
Main.c:10:5: note: while referencing ‘zal’
   10 | int zal[212345 * 2];
      |     ^~~

Judge Result