oj.uz

Submission #441604

# Submission time Handle Problem Language Result Execution time Memory
441604 2021-07-05T14:31:53 Z rainboy Fish (IOI08_fish) C
100 / 100
 846 ms 43952 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	500000
#define N_	(1 << 19)

unsigned int X = 12345;

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

int aa[N], jj[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 *eh[N], eo[N], eo_[N];

void append(int j, int h) {
	int o = eo[j]++;

	if (o >= 2 && (o & o - 1) == 0)
		eh[j] = (int *) realloc(eh[j], o * 2 * sizeof *eh[j]);
	eh[j][o] = h;
}

int md;

int st[N_ * 2], n_;

void pul(int i) {
	st[i] = st[i << 1 | 0] * st[i << 1 | 1] % md;
}

void build(int n, int k) {
	int i, j;

	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (i = 0; i < n_; i++)
		st[n_ + i] = 1;
	for (j = 0; j < k; j++)
		st[n_ + eh[j][0]] = (eo[j] + 1) % md;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int i, int x) {
	i += n_;
	st[i] = x;
	while (i > 1)
		pul(i >>= 1);
}

int query(int l, int r) {
	int x = 1;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			x = x * st[l++] % md;
		if ((r & 1) == 0)
			x = x * st[r--] % md;
	}
	return x;
}

int main() {
	static int ii[N], ll[N];
	int n, k, h, h_, i, j, ans;

	scanf("%d%d%d", &n, &k, &md);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &aa[i], &jj[i]), jj[i]--;
		ii[i] = i;
	}
	sort(ii, 0, n);
	for (j = 0; j < k; j++)
		eh[j] = (int *) malloc(2 * sizeof *eh[j]);
	for (h = 0; h < n; h++)
		append(jj[ii[h]], h);
	build(n, k);
	for (j = 0; j < k; j++)
		eo_[j] = eo[j];
	ans = 0;
	for (h = 0, h_ = 0; h < n; h++) {
		i = ii[h];
		while (h_ < n && aa[ii[h_]] >= aa[i] * 2)
			h_++;
		ll[h] = h_;
	}
	for (h = 0, h_ = 0; h < n; h++) {
		i = ii[h];
		while (h_ < n && aa[ii[h_]] * 2 > aa[i]) {
			j = jj[ii[h_++]];
			update(eh[j][0], eo_[j]-- % md);
		}
		j = jj[i];
		if (eh[j][0] == h) {
			int x = query(h + 1, n - 1), o;

			for (o = eo[j] - 1; o >= 0 && (o + 1 == eo[j] || aa[ii[eh[j][o + 1]]] * 2 <= aa[i]); o--)
				ans = (ans + x * query(ll[eh[j][o]], h - 1)) % md;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message

fish.c: In function 'append':
fish.c:39:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
fish.c: In function 'main':
fish.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d%d%d", &n, &k, &md);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fish.c:91:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   scanf("%d%d", &aa[i], &jj[i]), jj[i]--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 340 ms 20772 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 500 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9284 KB Output is correct
2 Correct 155 ms 10876 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 4 ms 588 KB Output is correct
3 Correct 4 ms 588 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 15140 KB Output is correct
2 Correct 369 ms 21368 KB Output is correct
3 Correct 352 ms 21532 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 21572 KB Output is correct
2 Correct 377 ms 22604 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 15440 KB Output is correct
2 Correct 380 ms 22012 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 20932 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 23324 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 20420 KB Output is correct
2 Correct 539 ms 26716 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 26488 KB Output is correct
2 Correct 391 ms 21080 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 25440 KB Output is correct
2 Correct 585 ms 26608 KB Output is correct
3 Correct 479 ms 29580 KB Output is correct
4 Correct 588 ms 26516 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 664 ms 30200 KB Output is correct
2 Correct 593 ms 42972 KB Output is correct
3 Correct 846 ms 43952 KB Output is correct
4 Correct 795 ms 39232 KB Output is correct