Submission #831578

#	Time	Username	Problem	Language	Result	Execution time	Memory
831578		rainboy	Sumtree (INOI20_sumtree)	C11	100 / 100	408 ms	48028 KiB

Main

#include <stdio.h>
#include <stdlib.h>

#define N	200000
#define A	300000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N + 1))) */
#define MD	1000000007
#define INF	0x3f3f3f3f

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

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

void init() {
	int i;

	ff[0] = gg[0] = 1;
	for (i = 1; i <= A + 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 *ej[N], eo[N];

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

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

int ta[N], tb[N], qu[N];

void dfs(int p, int i) {
	static int time;
	int o;

	qu[ta[i] = time++] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs(i, j);
	}
	tb[i] = time;
}

int h_, n_;

int mn[N_ * 2]; int kk[N_ * 2]; long long ss[N_ * 2]; int lz[N_];

void put(int i, int x) {
	mn[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1;

		if (mn[l] < mn[r])
			mn[i] = mn[l], kk[i] = kk[l], ss[i] = ss[l];
		else if (mn[l] > mn[r])
			mn[i] = mn[r], kk[i] = kk[r], ss[i] = ss[r];
		else
			mn[i] = mn[l], kk[i] = kk[l] + kk[r], ss[i] = ss[l] + ss[r];
	}
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void update(int l, int r, int x) {
	int l_, r_;

	if (l > r)
		return;
	l_ = l += n_, r_ = r += n_;
	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

void upd(int i, int k, int s) {
	i += n_;
	push(i), kk[i] = k, ss[i] = s, pull(i);
}

int query(int l, int r, int *k_, long long *s_) {
	int x, k;
	long long s;

	if (l > r) {
		*k_ = 0, *s_ = 0;
		return INF;
	}
	push(l += n_), push(r += n_);
	x = INF, k = 0, s = 0;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			if (x > mn[l])
				x = mn[l], k = 0, s = 0;
			if (x == mn[l])
				k += kk[l], s += ss[l];
			l++;
		}
		if ((r & 1) == 0) {
			if (x > mn[r])
				x = mn[r], k = 0, s = 0;
			if (x == mn[r])
				k += kk[r], s += ss[r];
			r--;
		}
	}
	*k_ = k, *s_ = s;
	return x;
}

int prev(int r) {
	int l, x;

	push(r += n_);
	x = mn[r];
	for (l = 0 + n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (mn[r] < x) {
				while (r < n_) {
					pus(r);
					r = mn[r << 1 | 1] < x ? r << 1 | 1 : r << 1 | 0;
				}
				return r - n_;
			}
			r--;
		}
	return -1;
}

int st[N_ * 2];

void pul_(int i) {
	st[i] = (long long) st[i << 1 | 0] * st[i << 1 | 1] % MD;
}

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

void build(int n) {
	int i;

	h_ = 0;
	while (1 << h_ <= n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++)
		st[n_ + i] = 1;
	for (i = n_ - 1; i > 0; i--)
		pul(i), pul_(i);
}

int main() {
	static int aa[N];
	int n, q, h, i, j, p;

	init();
	scanf("%d%d", &n, &aa[0]);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	dfs(-1, 0);
	build(n);
	update(1, n - 1, 1), upd(0, n, aa[0]);
	update_(0, choose(aa[0] + n - 1, n - 1));
	scanf("%d", &q);
	printf("%d\n", st[1]);
	while (q--) {
		int t, k;
		long long s;

		scanf("%d%d", &t, &i), i--;
		if (t == 1) {
			scanf("%d", &aa[i]);
			update(ta[i] + 1, tb[i] - 1, 1), upd(ta[i], tb[i] - ta[i], aa[i]);
			query(ta[i] + 1, tb[i] - 1, &k, &s);
			update_(ta[i], aa[i] < s ? 0 : choose(aa[i] - s + tb[i] - ta[i] - k - 1, tb[i] - ta[i] - k - 1));
			p = qu[prev(ta[i])];
			query(ta[p] + 1, tb[p] - 1, &k, &s);
			update_(ta[p], aa[p] < s ? 0 : choose(aa[p] - s + tb[p] - ta[p] - k - 1, tb[p] - ta[p] - k - 1));
		} else {
			update(ta[i] + 1, tb[i] - 1, -1), upd(ta[i], 0, 0);
			update_(ta[i], 1);
			p = qu[prev(ta[i])];
			query(ta[p] + 1, tb[p] - 1, &k, &s);
			update_(ta[p], aa[p] < s ? 0 : choose(aa[p] - s + tb[p] - ta[p] - k - 1, tb[p] - ta[p] - k - 1));
		}
		printf("%d\n", st[1]);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:34:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   34 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:195:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  195 |  scanf("%d%d", &n, &aa[0]);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~
Main.c:199:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:206:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
Main.c:212:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |   scanf("%d%d", &t, &i), i--;
      |   ^~~~~~~~~~~~~~~~~~~~~
Main.c:214:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  214 |    scanf("%d", &aa[i]);
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30