Submission #75599410

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>
#include <string.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];
int value[212345];
int* zaq(int q) {
  int l = 0, r = zac - 1;
  while (l <= r) {
    int m = l + (r - l) / 2;
    if (zal[m] == q) return &value[m];
    else if (zal[m] < q) l = m + 1;
    else r = m - 1;
  }
  return NULL;
}
int N;
int A[212345];
int main(void) {
  int i;
  int ans = 0;
  if (scanf("%d", &N) != 1) return 1;
  for (i = 0; i < N; i++) {
    if (scanf("%d", &A[i]) != 1) return 1;
  }
  memcpy(zal, A, sizeof(*A) * N);
  qsort(zal, N, sizeof(*zal), cmp);
  for (i = 1, zac = 1; i < N; i++) {
    if (zal[i] != zal[zac - 1]) zal[zac++] = zal[i];
  }
  for (i = N - 1; i >= 0; i--) {
    /* 「この先の、この要素値+1から始まる連続記録」+1 = この要素での記録 */
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>
#include <string.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];
int value[212345];

int* zaq(int q) {
	int l = 0, r = zac - 1;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (zal[m] == q) return &value[m];
		else if (zal[m] < q) l = m + 1;
		else r = m - 1;
	}
	return NULL;
}

int N;
int A[212345];

int main(void) {
	int i;
	int ans = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		if (scanf("%d", &A[i]) != 1) return 1;
	}
	memcpy(zal, A, sizeof(*A) * N);
	qsort(zal, N, sizeof(*zal), cmp);
	for (i = 1, zac = 1; i < N; i++) {
		if (zal[i] != zal[zac - 1]) zal[zac++] = zal[i];
	}
	for (i = N - 1; i >= 0; i--) {
		/* 「この先の、この要素値+1から始まる連続記録」+1 = この要素での記録 */
		int *pnext = zaq(A[i] + 1);
		int next_ans = pnext == NULL ? 0 : *pnext;
		int cur_ans;
		int *pcur = zaq(A[i]);
		if (pcur == NULL) return 72;
		cur_ans = next_ans + 1;
		if (*pcur < cur_ans) *pcur = cur_ans;
		if (cur_ans > ans) ans = cur_ans;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result