Submission #446920

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
446920	2021-07-23T19:23:59 Z	rainboy	Zoltan (COCI16_zoltan)	C	140 / 140	179 ms	8348 KB

zoltan

#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

#	Verdict	Execution time	Memory	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