oj.uz

Submission #417371

# Submission time Handle Problem Language Result Execution time Memory
417371 2021-06-03T15:42:13 Z parsabahrami Sumtree (INOI20_sumtree) C++17
50 / 100
 1436 ms 122108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii; 

#define SZ(x) (int) (x).size();
#define F     first
#define S     second

int Pow(int a, int b, int md, int ret = 1) {
	for (; b; b >>= 1, a = 1ll * a * a % md) 
		if (b & 1) ret = 1ll * ret * a % md;
	return ret;
}

const int N = 5e5 + 10, MOD = 1e9 + 7;
int F[N], St[N], Ft[N], I[N], hv[N], hd[N], S[N], P[N], val[N], H[N], n, q, R, timer;
vector<int> adj[N]; set<pii> st[N]; int ret;
struct node {
	ll d, lz; node *lc, *rc; 

	node() : d(0), lz(0), lc(nullptr), rc(nullptr) {}

	void bld(int l = 0, int r = n) {
		if (r - l < 2) return;
		lc = new node(); rc = new node();
		int md = (l + r) >> 1;
		lc->bld(l, md), rc->bld(md, r);
	}

	void shift() { 
		if (!lz) return;
		d += lz;
		if (lc) lc->lz += lz;
		if (rc) rc->lz += lz;
		lz = 0;
	}

	void upd(int ql, int qr, ll x, int l = 0, int r = n) {
		shift();
		if (qr <= l || r <= ql) return;
		if (ql <= l && r <= qr) { lz += x; return shift(); }
		int md = (l + r) >> 1;
		lc->upd(ql, qr, x, l, md), rc->upd(ql, qr, x, md, r);
		d = min(lc->d, rc->d);
	}

	ll get(int p, int l = 0, int r = n) {
        shift();
		if (r - l < 2) return d;
		int md = (l + r) >> 1;
		return p < md ? lc->get(p, l, md) : rc->get(p, md, r);
	}
};
node *A, *B;

void preDFS(int v, int p = -1) {
	S[v] = 1; P[v] = p;
	for (int u : adj[v]) 
		if (u != p) { H[u] = H[v] + 1, preDFS(u, v), S[v] += S[u];
			if (S[hv[v]] < S[u]) hv[v] = u; }
}

void hldDFS(int v, int p = -1) {
	if (!~p) hd[v] = v;
	St[v] = timer++;
	if (hv[v]) 
		hd[hv[v]] = hd[v], hldDFS(hv[v], v);
	for (int u : adj[v])
		if (u != p && u != hv[v]) 
			hldDFS(hd[u] = u, v);
	Ft[v] = timer;
}

int C(int x, int y) {
	if (x < y || y < 0) return 0;
	return F[x] * 1ll * I[y] % MOD * I[x - y] % MOD;
}

int main() {
	scanf("%d%d", &n, &R);
	F[0] = 1; st[1].insert(pii(0, 1)); val[1] = R;
	for (int i = 1; i < N; i++)  
		F[i] = 1ll * F[i - 1] * i % MOD;
	I[N - 1] = Pow(F[N - 1], MOD - 2, MOD);
	for (int i = N - 1; i; i--) 
		I[i - 1] = 1ll * I[i] * i % MOD;
	for (int i = 1; i < n; i++) {
		int u, v; scanf("%d%d", &u, &v); 
		adj[u].push_back(v);
		adj[v].push_back(u);
	} 
	A = new node(), B = new node(); A->bld(), B->bld(); B->upd(0, 1, R);
	preDFS(1); hldDFS(1);
	printf("%d\n", ret = C(R + n - 1, n - 1));
	for (int i = 1; i <= n; i++) 
		A->upd(St[i], St[i] + 1, S[i]);
	for (scanf("%d", &q); q; q--) {
		int t, v, x; scanf("%d%d", &t, &v);
		if (t < 2) {
			scanf("%d", &x); int sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
			int y = B->get(St[v]); val[v] = x;
			ret = 1ll * ret * C(y + sub - 1, sub - 1) % MOD;
			int u = P[v];
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[u]) {
				A->upd(St[hd[u]], St[u] + 1, -sub); 
				B->upd(St[hd[u]], St[u] + 1, -y);
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			st[hd[v]].insert(pii(St[v], v));
			int cpr = A->get(St[pr]); int z = B->get(St[pr]);
			ret = 1ll * ret * Pow(C(cpr - 1 + z, z), MOD - 2, MOD) % MOD;
			A->upd(St[pr], St[u] + 1, -sub); B->upd(St[pr], St[u] + 1, -y); 
			z = B->get(St[pr]); cpr = A->get(St[pr]);
			ret = 1ll * ret * C(cpr - 1 + z, z) % MOD;
		} else {
            int sub = A->get(St[v]), y = B->get(St[v]);
			ret = 1ll * ret * Pow(C(y + sub - 1, sub - 1), MOD - 2, MOD) % MOD;
			int u = P[v]; st[hd[v]].erase({St[v], v});
			while (st[hd[u]].empty() || st[hd[u]].begin()->F > St[u]) {
				A->upd(St[hd[u]], St[u] + 1, sub); 
				B->upd(St[hd[u]], St[u] + 1, y);
				u = P[hd[u]]; 
			}
			int pr = prev(st[hd[u]].lower_bound(pii(St[u], n + 1)))->S;
			int cpr = A->get(St[pr]); int z = B->get(St[pr]); 
			ret = 1ll * ret * Pow(C(cpr - 1 + z, z), MOD - 2, MOD) % MOD;
			A->upd(St[pr], St[u] + 1, sub); B->upd(St[pr], St[u] + 1, y); 
			z = B->get(St[pr]); cpr = A->get(St[pr]); 
			ret = 1ll * ret * C(cpr - 1 + z, z) % MOD; B->upd(St[v], St[v] + 1, -val[v]);
		}
		printf("%d\n", ret);
	}
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d%d", &n, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:100:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  for (scanf("%d", &q); q; q--) {
      |       ~~~~~^~~~~~~~~~
Main.cpp:101:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |   int t, v, x; scanf("%d%d", &t, &v);
      |                ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |    scanf("%d", &x); int sub = A->get(St[v]); B->upd(St[v], St[v] + 1, x);
      |    ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 100548 KB Output is correct
2 Correct 295 ms 100608 KB Output is correct
3 Correct 295 ms 100664 KB Output is correct
4 Correct 296 ms 100708 KB Output is correct
5 Correct 254 ms 95940 KB Output is correct
6 Correct 34 ms 40436 KB Output is correct
7 Correct 33 ms 40172 KB Output is correct
8 Correct 34 ms 40264 KB Output is correct
9 Correct 348 ms 91428 KB Output is correct
10 Correct 341 ms 91184 KB Output is correct
11 Correct 337 ms 91332 KB Output is correct
12 Correct 324 ms 88932 KB Output is correct
13 Correct 249 ms 95448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 39364 KB Output is correct
2 Correct 30 ms 39360 KB Output is correct
3 Correct 31 ms 39388 KB Output is correct
4 Correct 31 ms 39496 KB Output is correct
5 Correct 32 ms 39576 KB Output is correct
6 Correct 37 ms 40012 KB Output is correct
7 Correct 36 ms 40012 KB Output is correct
8 Correct 37 ms 40000 KB Output is correct
9 Correct 39 ms 40260 KB Output is correct
10 Correct 40 ms 40464 KB Output is correct
11 Correct 40 ms 40396 KB Output is correct
12 Correct 34 ms 40268 KB Output is correct
13 Correct 38 ms 40336 KB Output is correct
14 Correct 39 ms 40296 KB Output is correct
15 Correct 40 ms 40492 KB Output is correct
16 Correct 39 ms 40268 KB Output is correct
17 Correct 39 ms 40352 KB Output is correct
18 Correct 37 ms 39804 KB Output is correct
19 Correct 40 ms 40268 KB Output is correct
20 Correct 36 ms 39912 KB Output is correct
21 Correct 36 ms 40004 KB Output is correct
22 Correct 32 ms 39488 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 101008 KB Output is correct
2 Correct 398 ms 101964 KB Output is correct
3 Correct 324 ms 101704 KB Output is correct
4 Correct 463 ms 103588 KB Output is correct
5 Correct 687 ms 102592 KB Output is correct
6 Correct 35 ms 40516 KB Output is correct
7 Correct 34 ms 40276 KB Output is correct
8 Correct 36 ms 40364 KB Output is correct
9 Correct 798 ms 97884 KB Output is correct
10 Correct 736 ms 96452 KB Output is correct
11 Correct 676 ms 96188 KB Output is correct
12 Correct 801 ms 96432 KB Output is correct
13 Correct 654 ms 122108 KB Output is correct
14 Correct 667 ms 121924 KB Output is correct
15 Correct 661 ms 121992 KB Output is correct
16 Correct 646 ms 121732 KB Output is correct
17 Correct 657 ms 121632 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 94912 KB Output is correct
2 Correct 1417 ms 93896 KB Output is correct
3 Correct 1422 ms 93812 KB Output is correct
4 Correct 1369 ms 94004 KB Output is correct
5 Correct 1350 ms 91112 KB Output is correct
6 Correct 1436 ms 93888 KB Output is correct
7 Correct 1030 ms 68732 KB Output is correct
8 Correct 990 ms 68676 KB Output is correct
9 Correct 1432 ms 93780 KB Output is correct
10 Correct 1323 ms 93796 KB Output is correct
11 Correct 1293 ms 93764 KB Output is correct
12 Correct 966 ms 68676 KB Output is correct
13 Incorrect 702 ms 66828 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 100548 KB Output is correct
2 Correct 295 ms 100608 KB Output is correct
3 Correct 295 ms 100664 KB Output is correct
4 Correct 296 ms 100708 KB Output is correct
5 Correct 254 ms 95940 KB Output is correct
6 Correct 34 ms 40436 KB Output is correct
7 Correct 33 ms 40172 KB Output is correct
8 Correct 34 ms 40264 KB Output is correct
9 Correct 348 ms 91428 KB Output is correct
10 Correct 341 ms 91184 KB Output is correct
11 Correct 337 ms 91332 KB Output is correct
12 Correct 324 ms 88932 KB Output is correct
13 Correct 249 ms 95448 KB Output is correct
14 Correct 30 ms 39364 KB Output is correct
15 Correct 30 ms 39360 KB Output is correct
16 Correct 31 ms 39388 KB Output is correct
17 Correct 31 ms 39496 KB Output is correct
18 Correct 32 ms 39576 KB Output is correct
19 Correct 37 ms 40012 KB Output is correct
20 Correct 36 ms 40012 KB Output is correct
21 Correct 37 ms 40000 KB Output is correct
22 Correct 39 ms 40260 KB Output is correct
23 Correct 40 ms 40464 KB Output is correct
24 Correct 40 ms 40396 KB Output is correct
25 Correct 34 ms 40268 KB Output is correct
26 Correct 38 ms 40336 KB Output is correct
27 Correct 39 ms 40296 KB Output is correct
28 Correct 40 ms 40492 KB Output is correct
29 Correct 39 ms 40268 KB Output is correct
30 Correct 39 ms 40352 KB Output is correct
31 Correct 37 ms 39804 KB Output is correct
32 Correct 40 ms 40268 KB Output is correct
33 Correct 36 ms 39912 KB Output is correct
34 Correct 36 ms 40004 KB Output is correct
35 Correct 32 ms 39488 KB Output is correct
36 Correct 340 ms 101008 KB Output is correct
37 Correct 398 ms 101964 KB Output is correct
38 Correct 324 ms 101704 KB Output is correct
39 Correct 463 ms 103588 KB Output is correct
40 Correct 687 ms 102592 KB Output is correct
41 Correct 35 ms 40516 KB Output is correct
42 Correct 34 ms 40276 KB Output is correct
43 Correct 36 ms 40364 KB Output is correct
44 Correct 798 ms 97884 KB Output is correct
45 Correct 736 ms 96452 KB Output is correct
46 Correct 676 ms 96188 KB Output is correct
47 Correct 801 ms 96432 KB Output is correct
48 Correct 654 ms 122108 KB Output is correct
49 Correct 667 ms 121924 KB Output is correct
50 Correct 661 ms 121992 KB Output is correct
51 Correct 646 ms 121732 KB Output is correct
52 Correct 657 ms 121632 KB Output is correct
53 Correct 1422 ms 94912 KB Output is correct
54 Correct 1417 ms 93896 KB Output is correct
55 Correct 1422 ms 93812 KB Output is correct
56 Correct 1369 ms 94004 KB Output is correct
57 Correct 1350 ms 91112 KB Output is correct
58 Correct 1436 ms 93888 KB Output is correct
59 Correct 1030 ms 68732 KB Output is correct
60 Correct 990 ms 68676 KB Output is correct
61 Correct 1432 ms 93780 KB Output is correct
62 Correct 1323 ms 93796 KB Output is correct
63 Correct 1293 ms 93764 KB Output is correct
64 Correct 966 ms 68676 KB Output is correct
65 Incorrect 702 ms 66828 KB Output isn't correct
66 Halted 0 ms 0 KB -