oj.uz

Submission #486381

# Submission time Handle Problem Language Result Execution time Memory
486381 2021-11-11T13:42:36 Z rainboy Žarulje (COI15_zarulje) C
60 / 100
 1000 ms 5328 KB 
#include <stdio.h>

#define N	200000
#define MD	1000000007

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

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

int vv[N + 1], ff[N + 1], gg[N + 1];

void init() {
	int i;

	ff[0] = gg[0] = 1;
	for (i = 1; i <= N; i++) {
		vv[i] = i == 1 ? 1 : (long long) vv[i - MD % i] * (MD / i + 1) % MD;
		ff[i] = (long long) ff[i - 1] * i % MD;
		gg[i] = (long long) gg[i - 1] * vv[i] % MD;
	}
}

int choose(int n, int k) {
	return (long long) ff[n] * gg[k] % MD * gg[n - k] % MD;
}

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) {
			int c = aa[ii[j]] != aa[i_] ? aa[ii[j]] - aa[i_] : ii[j] - i_;

			if (c == 0)
				j++;
			else if (c < 0) {
				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 main() {
	static int ii[N];
	int n, k, h, i, j;

	init();
	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++) {
		scanf("%d", &aa[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	while (k--) {
		int l, r, c, ans;

		scanf("%d", &c), c--;
		l = 0, r = n - 1, ans = 1;
		for (i = 0; i < n; i = j) {
			int l_, r_, kl, kr;

			j = i + 1;
			while (j < n && aa[ii[j]] == aa[ii[i]])
				j++;
			l_ = l, r_ = r, kl = kr = 0;
			for (h = i; h < j; h++) {
				if (ii[h] == c || ii[h] < l || ii[h] > r)
					continue;
				if (ii[h] < c)
					l_ = max(l_, ii[h] + 1), kl++;
				if (ii[h] > c)
					r_ = min(r_, ii[h] - 1), kr++;
			}
			ans = (long long) ans * choose(kl + kr, kl) % MD;
			l = l_, r = r_;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Compilation message

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

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 11 ms 2688 KB Output is correct
4 Correct 22 ms 2648 KB Output is correct
5 Correct 22 ms 2672 KB Output is correct
6 Correct 36 ms 2636 KB Output is correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3404 KB Output is correct
2 Correct 50 ms 4556 KB Output is correct
3 Correct 58 ms 4740 KB Output is correct
4 Correct 54 ms 4860 KB Output is correct
5 Correct 57 ms 5064 KB Output is correct
6 Correct 72 ms 5328 KB Output is correct
7 Correct 69 ms 5320 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Correct 4 ms 2636 KB Output is correct
3 Correct 11 ms 2688 KB Output is correct
4 Correct 22 ms 2648 KB Output is correct
5 Correct 22 ms 2672 KB Output is correct
6 Correct 36 ms 2636 KB Output is correct
7 Correct 27 ms 3404 KB Output is correct
8 Correct 50 ms 4556 KB Output is correct
9 Correct 58 ms 4740 KB Output is correct
10 Correct 54 ms 4860 KB Output is correct
11 Correct 57 ms 5064 KB Output is correct
12 Correct 72 ms 5328 KB Output is correct
13 Correct 69 ms 5320 KB Output is correct
14 Correct 203 ms 2792 KB Output is correct
15 Execution timed out 1090 ms 4148 KB Time limit exceeded
16 Halted 0 ms 0 KB -