Submission #441604

#	Time	Username	Problem	Language	Result	Execution time	Memory
441604		rainboy	Fish (IOI08_fish)	C11	100 / 100	846 ms	43952 KiB

fish

#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 (stderr)

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 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 7 / 7
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5