Submission #63918852

---

Source Code Expand

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

#define INF 1010101010

struct node_s {
	int value;
	struct node_s* next[2];
};

int array_get(const struct node_s* node, int idx) {
	if (node == NULL) return INF;
	if (idx == 0) return node->value;
	return array_get(node->next[idx & 1], idx >> 1);
}

struct node_s* array_set(const struct node_s* node, int idx, int value) {
	struct node_s* res = malloc(sizeof(*res));
	if (res == NULL) exit(2);
	if (node != NULL) {
		*res = *node;
	} else {
		res->value = INF;
		res->next[0] = NULL;
		res->next[1] = NULL;
	}
	if (idx == 0) {
		res->value = value;
	} else {
		res->next[idx & 1] = array_set(res->next[idx & 1], idx >> 1, value);
	}
	return res;
}

int N, Q;
int A[212345];
int R[212345], X[212345];

int lis_num[212345];
struct node_s* lis[212345];

int main(void) {
	int i;
	if (scanf("%d%d", &N, &Q) != 2) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	for (i = 0; i < Q; i++) {
		if (scanf("%d%d", &R[i], &X[i]) != 2) return 1;
	}

	for (i = 1; i <= N; i++) {
		int l = -1, ge = lis_num[i - 1];
		while (l + 1 < ge) {
			int m = l + (ge - l) / 2;
			if (array_get(lis[i - 1], m) >= A[i]) ge = m; else l = m;
		}
		lis[i] = array_set(lis[i - 1], ge, A[i]);
		lis_num[i] = lis_num[i - 1] + (ge >= lis_num[i - 1]);
	}

	for (i = 0; i < Q; i++) {
		int le = -1, g = lis_num[R[i]];
		while (le + 1 < g) {
			int m = le + (g - le) / 2;
			if (array_get(lis[R[i]], m) <= X[i]) le = m; else g = m;
		}
		printf("%d\n", le + 1);
	}

	return 0;
}

/*

それぞれの A_i ごとに、よくあるLISのやつをやる
永続配列？を使う → 連想配列でやる
配列の中身 → その長さにできる、一番大きいやつの最小


*/

Submission Info

Judge Result