oj.uz

답안 #446920

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
446920 2021-07-23T19:23:59 Z rainboy Zoltan (COCI16_zoltan) C
140 / 140
 179 ms 8348 KB 
#include <stdio.h>
#include <string.h>

#define N	200000
#define MD	1000000007

unsigned int X;

int rand_() {
	return (X *= 3) >> 1;
}

int aa[N];

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (aa[ii[j]] == aa[i_])
				j++;
			else if (aa[ii[j]] < aa[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int ft1[N], ft2[N];

void update(int i, int n, int x, int y) {
	while (i < n) {
		if (ft1[i] < x)
			ft1[i] = x, ft2[i] = 0;
		if (ft1[i] == x)
			ft2[i] = (ft2[i] + y) % MD;
		i |= i + 1;
	}
}

void query(int i, int *x, int *y) {
	*x = 0, *y = 1;
	while (i >= 0) {
		if (*x < ft1[i])
			*x = ft1[i], *y = 0;
		if (*x == ft1[i])
			*y = (*y + ft2[i]) % MD;
		i &= i + 1, i--;
	}
}

int main() {
	static int ii[N], dp1[N], dp2[N], dq1[N], dq2[N];
	int n, i, a, x_, y_;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	for (i = 0, a = 0; i < n; i++)
		aa[ii[i]] = i + 1 == n || aa[ii[i + 1]] != aa[ii[i]] ? a++ : a;
	memset(ft1, 0, n * sizeof *ft1), memset(ft2, 0, n * sizeof *ft2);
	for (i = n - 1; i >= 0; i--)
		query(aa[i] - 1, &dp1[i], &dp2[i]), dp1[i]++, update(aa[i], n, dp1[i], dp2[i]);
	memset(ft1, 0, n * sizeof *ft1), memset(ft2, 0, n * sizeof *ft2);
	for (i = n - 1; i >= 0; i--)
		query(n - 1 - aa[i] - 1, &dq1[i], &dq2[i]), dq1[i]++, update(n - 1 - aa[i], n, dq1[i], dq2[i]);
	x_ = -1, y_ = 0;
	for (i = 0; i < n; i++) {
		int x = dp1[i] + dq1[i] - 1, y = (long long) dp2[i] * dq2[i] % MD;

		if (x_ < x)
			x_ = x, y_ = 0;
		if (x_ == x)
			y_ = (y_ + y) % MD;
	}
	for (i = 0; i < n - x_; i++)
		y_ = y_ * 2 % MD;
	printf("%d %d\n", x_, y_);
	return 0;
}

Compilation message

zoltan.c: In function 'main':
zoltan.c:61:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
zoltan.c:63:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 179 ms 6452 KB Output is correct
12 Correct 144 ms 5572 KB Output is correct
13 Correct 135 ms 5228 KB Output is correct
14 Correct 77 ms 5828 KB Output is correct
15 Correct 100 ms 7292 KB Output is correct
16 Correct 116 ms 8348 KB Output is correct
17 Correct 96 ms 7764 KB Output is correct
18 Correct 95 ms 7664 KB Output is correct
19 Correct 103 ms 7728 KB Output is correct
20 Correct 92 ms 7664 KB Output is correct