Submission #74965803

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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 N, Q;
int A[312345];
int X[312345], Y[312345];
/* A に query 以下の整数が何個あるか */
int asumikana(int query) {
  int le = -1, g = N;
  while (le + 1 < g) {
    int m = le + (g - le) / 2;
    if (A[m] <= query) le = m; else g = m;
  }
  return g;
}
/* query 以下の正の整数で、A に含まれないものが何個あるか */
int kitamuraeri(int query) {
  if (query <= 0) return 0;
  return query - asumikana(query);
}
int main(void) {
  int i;
  if (scanf("%d%d", &N, &Q) != 2) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d", &A[i]) != 1) return 1;
  }
  for (i = 0; i < Q; i++) {
    if (scanf("%d%d", &X[i], &Y[i]) != 2) return 1;
  }
  qsort(A, N, sizeof(*A), cmp);
  for (i = 0; i < Q; i++) {
    int exclude = kitamuraeri(X[i] - 1);
    int l = X[i] - 1, ge = 2020202020;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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 N, Q;
int A[312345];
int X[312345], Y[312345];

/* A に query 以下の整数が何個あるか */
int asumikana(int query) {
	int le = -1, g = N;
	while (le + 1 < g) {
		int m = le + (g - le) / 2;
		if (A[m] <= query) le = m; else g = m;
	}
	return g;
}

/* query 以下の正の整数で、A に含まれないものが何個あるか */
int kitamuraeri(int query) {
	if (query <= 0) return 0;
	return query - asumikana(query);
}

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &X[i], &Y[i]) != 2) return 1;
	}
	qsort(A, N, sizeof(*A), cmp);
	for (i = 0; i < Q; i++) {
		int exclude = kitamuraeri(X[i] - 1);
		int l = X[i] - 1, ge = 2020202020;
		while (l + 1 < ge) {
			int m = l + (ge - l) / 2;
			int check = kitamuraeri(m) - exclude;
			if (check >= Y[i]) ge = m; else l = m;
		}
		printf("%d\n", ge);
	}
	return 0;
}

Submission Info

Judge Result