oj.uz

Submission #831577

# Submission time Handle Problem Language Result Execution time Memory
831577 2023-08-20T10:40:15 Z rainboy Sumtree (INOI20_sumtree) C
10 / 100
 355 ms 36268 KB 
#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(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(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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 32060 KB Output is correct
2 Correct 71 ms 32168 KB Output is correct
3 Correct 73 ms 32172 KB Output is correct
4 Correct 69 ms 32164 KB Output is correct
5 Correct 70 ms 28948 KB Output is correct
6 Correct 9 ms 6596 KB Output is correct
7 Correct 7 ms 6432 KB Output is correct
8 Correct 7 ms 6460 KB Output is correct
9 Correct 73 ms 26184 KB Output is correct
10 Correct 69 ms 26136 KB Output is correct
11 Correct 106 ms 26188 KB Output is correct
12 Correct 66 ms 25460 KB Output is correct
13 Correct 61 ms 30700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 36268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 33272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 32060 KB Output is correct
2 Correct 71 ms 32168 KB Output is correct
3 Correct 73 ms 32172 KB Output is correct
4 Correct 69 ms 32164 KB Output is correct
5 Correct 70 ms 28948 KB Output is correct
6 Correct 9 ms 6596 KB Output is correct
7 Correct 7 ms 6432 KB Output is correct
8 Correct 7 ms 6460 KB Output is correct
9 Correct 73 ms 26184 KB Output is correct
10 Correct 69 ms 26136 KB Output is correct
11 Correct 106 ms 26188 KB Output is correct
12 Correct 66 ms 25460 KB Output is correct
13 Correct 61 ms 30700 KB Output is correct
14 Incorrect 8 ms 6164 KB Output isn't correct
15 Halted 0 ms 0 KB -