提出 #45706250

ソースコード 拡げる

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 ? -1 : a > b;
}
int zac;
int zal[612345];
int zaq(int q) {
  int l = 0, r = zac - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (zal[m] == q) return m;
    else if (zal[m] < q) l = m + 1;
    else r = m - 1;
  }
  printf("ERROR: %d not found\n", q);
  exit(99);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#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 ? -1 : a > b;
}

int zac;
int zal[612345];

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

int N;
int A[212345];
int Q;
int l[212345];
int r[212345];

char neteru[612345];
int neteru_ruiseki[612345];

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

/*

0 --- 1 --- 2 +++ 3 +++ 4 +++ 5 --- 6 (index)
0     5     7    12    18    21    25 (zal)
0     0     1     1     1     0     0 (neteru)
0     0     0     5    11    14    14 (neteru_ruiseki)

*/

提出情報

ジャッジ結果