oj.uz

Submission #1060309

# Submission time Handle Problem Language Result Execution time Memory
1060309 2024-08-15T12:52:41 Z DorostWef Digital Circuit (IOI22_circuit) C++17
100 / 100
 775 ms 36552 KB 
#include "circuit.h"

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
#define int long long
const int N = 200023, M = 1000002022;
int a[N], p[N];
int ans[N];
int st[N];
vector <int> g[N];
int pre[N], suf[N];
int x[N];

void predfs (int v) {
	int sz = (int)g[v].size();
	if (sz == 0) {
		st[v] = 1;
		return;
	}
	st[v] = sz;
	for (int u : g[v]) {
		predfs (u);
		st[v] = (st[v] * st[u]) % M;
	}
}

void dfs (int v) {
	int sz = (int)g[v].size();
	if (sz == 0) {
		return;
	}
	pre[0] = 1;
	suf[sz] = 1;
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		pre[i + 1] = (pre[i] * st[u]) % M;
	}
	for (int i = sz - 1; i >= 0; i--) {
		int u = g[v][i];
		suf[i] = (suf[i + 1] * st[u]) % M;
	}
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		ans[u] = (ans[v] * ((pre[i] * suf[i + 1]) % M) % M);
	}
	for (int i = 0; i < sz; i++) {
		int u = g[v][i];
		dfs (u);
	}
}

int m, n;

const int SegN = (1 << 19);
int seg[SegN], sum[SegN];
bool lz[SegN];

void build (int v = 1, int tl = 0, int tr = N - 1) {
	lz[v] = false;
	if (tl == tr) {
		seg[v] = a[tl] * p[tl];
		sum[v] = p[tl];
	} else {
		int mid = (tl + tr) >> 1;
		build (v << 1, tl, mid);
		build (v << 1 | 1, mid + 1, tr);
		seg[v] = seg[v << 1 | 1] + seg[v << 1];
		sum[v] = sum[v << 1 | 1] + sum[v << 1];
	}
}

void shift (int v) {
	if (lz[v]) {
		seg[v << 1] = sum[v << 1] - seg[v << 1];
		seg[v << 1 | 1] = sum[v << 1 | 1] - seg[v << 1 | 1];
		lz[v << 1] ^= 1;
		lz[v << 1 | 1] ^= 1;
		lz[v] = 0;
	}
}

void upd (int l, int r, int v = 1, int tl = 0, int tr = N - 1) {
	if (l > tr || tl > r)
		return;
	if (l <= tl && tr <= r) {
		seg[v] = sum[v] - seg[v];
		lz[v] ^= 1;
		return;
	}
	shift (v);
	int mid = (tl + tr) >> 1;
	upd (l, r, v << 1, tl, mid);
	upd (l, r, v << 1 | 1, mid + 1, tr);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
	n = N;
	for (int i = 0; i < N + M; i++) {
		g[P[i]].push_back(i);
	}
	m = M;
	for (int i = 0; i < M; i++)
		a[i] = A[i];
	predfs (0);
	ans[0] = 1;
	dfs (0);
	for (int i = 0; i < M; i++)
		p[i] = ans[i + N];
	build();
}

int32_t count_ways(int32_t L, int32_t R) {
	L -= n;
	R -= n;
	upd (L, R);
	return seg[1] % M;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23128 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 4 ms 23172 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23128 KB Output is correct
7 Correct 4 ms 23208 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23128 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23128 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23172 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 4 ms 23128 KB Output is correct
15 Correct 4 ms 23208 KB Output is correct
16 Correct 4 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 4 ms 23128 KB Output is correct
20 Correct 4 ms 23128 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 5 ms 23080 KB Output is correct
23 Correct 4 ms 23380 KB Output is correct
24 Correct 4 ms 23128 KB Output is correct
25 Correct 4 ms 23064 KB Output is correct
26 Correct 4 ms 23128 KB Output is correct
27 Correct 4 ms 23128 KB Output is correct
28 Correct 4 ms 23128 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
30 Correct 4 ms 23128 KB Output is correct
31 Correct 4 ms 23128 KB Output is correct
32 Correct 4 ms 23128 KB Output is correct
33 Correct 4 ms 23128 KB Output is correct
34 Correct 4 ms 23128 KB Output is correct
35 Correct 4 ms 23052 KB Output is correct
36 Correct 4 ms 23128 KB Output is correct
37 Correct 4 ms 23128 KB Output is correct
38 Correct 4 ms 23128 KB Output is correct
39 Correct 3 ms 23128 KB Output is correct
40 Correct 4 ms 23128 KB Output is correct
41 Correct 5 ms 23228 KB Output is correct
42 Correct 3 ms 23160 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 25176 KB Output is correct
2 Correct 633 ms 27224 KB Output is correct
3 Correct 612 ms 27088 KB Output is correct
4 Correct 648 ms 27224 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 25176 KB Output is correct
2 Correct 633 ms 27224 KB Output is correct
3 Correct 612 ms 27088 KB Output is correct
4 Correct 648 ms 27224 KB Output is correct
5 Correct 518 ms 25176 KB Output is correct
6 Correct 652 ms 27224 KB Output is correct
7 Correct 682 ms 27216 KB Output is correct
8 Correct 656 ms 27092 KB Output is correct
9 Correct 288 ms 23128 KB Output is correct
10 Correct 638 ms 23384 KB Output is correct
11 Correct 621 ms 23384 KB Output is correct
12 Correct 651 ms 23384 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 4 ms 23172 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23128 KB Output is correct
7 Correct 4 ms 23208 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23128 KB Output is correct
13 Correct 463 ms 25176 KB Output is correct
14 Correct 633 ms 27224 KB Output is correct
15 Correct 612 ms 27088 KB Output is correct
16 Correct 648 ms 27224 KB Output is correct
17 Correct 518 ms 25176 KB Output is correct
18 Correct 652 ms 27224 KB Output is correct
19 Correct 682 ms 27216 KB Output is correct
20 Correct 656 ms 27092 KB Output is correct
21 Correct 288 ms 23128 KB Output is correct
22 Correct 638 ms 23384 KB Output is correct
23 Correct 621 ms 23384 KB Output is correct
24 Correct 651 ms 23384 KB Output is correct
25 Correct 629 ms 29236 KB Output is correct
26 Correct 674 ms 29264 KB Output is correct
27 Correct 740 ms 29260 KB Output is correct
28 Correct 552 ms 29260 KB Output is correct
29 Correct 624 ms 35664 KB Output is correct
30 Correct 646 ms 35660 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23128 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23172 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 4 ms 23128 KB Output is correct
15 Correct 4 ms 23208 KB Output is correct
16 Correct 4 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 4 ms 23128 KB Output is correct
20 Correct 4 ms 23128 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 5 ms 23080 KB Output is correct
23 Correct 4 ms 23380 KB Output is correct
24 Correct 4 ms 23128 KB Output is correct
25 Correct 4 ms 23064 KB Output is correct
26 Correct 4 ms 23128 KB Output is correct
27 Correct 4 ms 23128 KB Output is correct
28 Correct 4 ms 23128 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
30 Correct 4 ms 23128 KB Output is correct
31 Correct 4 ms 23128 KB Output is correct
32 Correct 4 ms 23128 KB Output is correct
33 Correct 4 ms 23128 KB Output is correct
34 Correct 4 ms 23128 KB Output is correct
35 Correct 4 ms 23052 KB Output is correct
36 Correct 4 ms 23128 KB Output is correct
37 Correct 4 ms 23128 KB Output is correct
38 Correct 4 ms 23128 KB Output is correct
39 Correct 3 ms 23128 KB Output is correct
40 Correct 4 ms 23128 KB Output is correct
41 Correct 5 ms 23228 KB Output is correct
42 Correct 3 ms 23160 KB Output is correct
43 Correct 490 ms 23128 KB Output is correct
44 Correct 662 ms 23384 KB Output is correct
45 Correct 667 ms 23384 KB Output is correct
46 Correct 623 ms 23384 KB Output is correct
47 Correct 686 ms 23380 KB Output is correct
48 Correct 624 ms 23384 KB Output is correct
49 Correct 669 ms 23384 KB Output is correct
50 Correct 634 ms 23384 KB Output is correct
51 Correct 614 ms 23384 KB Output is correct
52 Correct 656 ms 23384 KB Output is correct
53 Correct 585 ms 23892 KB Output is correct
54 Correct 588 ms 23384 KB Output is correct
55 Correct 590 ms 23384 KB Output is correct
56 Correct 647 ms 23384 KB Output is correct
57 Correct 644 ms 23128 KB Output is correct
58 Correct 625 ms 23700 KB Output is correct
59 Correct 598 ms 23896 KB Output is correct
60 Correct 611 ms 23896 KB Output is correct
61 Correct 601 ms 23384 KB Output is correct
62 Correct 650 ms 23128 KB Output is correct
63 Correct 586 ms 23128 KB Output is correct
64 Correct 531 ms 23128 KB Output is correct
65 Correct 282 ms 23128 KB Output is correct
66 Correct 602 ms 23384 KB Output is correct
67 Correct 499 ms 23384 KB Output is correct
68 Correct 560 ms 23384 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23128 KB Output is correct
2 Correct 4 ms 23128 KB Output is correct
3 Correct 4 ms 23128 KB Output is correct
4 Correct 5 ms 23128 KB Output is correct
5 Correct 4 ms 23128 KB Output is correct
6 Correct 4 ms 23128 KB Output is correct
7 Correct 3 ms 23128 KB Output is correct
8 Correct 4 ms 23128 KB Output is correct
9 Correct 4 ms 23128 KB Output is correct
10 Correct 4 ms 23128 KB Output is correct
11 Correct 4 ms 23128 KB Output is correct
12 Correct 4 ms 23172 KB Output is correct
13 Correct 4 ms 23128 KB Output is correct
14 Correct 4 ms 23128 KB Output is correct
15 Correct 4 ms 23208 KB Output is correct
16 Correct 4 ms 23128 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 23128 KB Output is correct
19 Correct 4 ms 23128 KB Output is correct
20 Correct 4 ms 23128 KB Output is correct
21 Correct 4 ms 23128 KB Output is correct
22 Correct 5 ms 23080 KB Output is correct
23 Correct 4 ms 23380 KB Output is correct
24 Correct 4 ms 23128 KB Output is correct
25 Correct 4 ms 23064 KB Output is correct
26 Correct 4 ms 23128 KB Output is correct
27 Correct 4 ms 23128 KB Output is correct
28 Correct 4 ms 23128 KB Output is correct
29 Correct 4 ms 23128 KB Output is correct
30 Correct 4 ms 23128 KB Output is correct
31 Correct 4 ms 23128 KB Output is correct
32 Correct 4 ms 23128 KB Output is correct
33 Correct 4 ms 23128 KB Output is correct
34 Correct 4 ms 23128 KB Output is correct
35 Correct 4 ms 23052 KB Output is correct
36 Correct 4 ms 23128 KB Output is correct
37 Correct 4 ms 23128 KB Output is correct
38 Correct 4 ms 23128 KB Output is correct
39 Correct 3 ms 23128 KB Output is correct
40 Correct 4 ms 23128 KB Output is correct
41 Correct 5 ms 23228 KB Output is correct
42 Correct 3 ms 23160 KB Output is correct
43 Correct 463 ms 25176 KB Output is correct
44 Correct 633 ms 27224 KB Output is correct
45 Correct 612 ms 27088 KB Output is correct
46 Correct 648 ms 27224 KB Output is correct
47 Correct 518 ms 25176 KB Output is correct
48 Correct 652 ms 27224 KB Output is correct
49 Correct 682 ms 27216 KB Output is correct
50 Correct 656 ms 27092 KB Output is correct
51 Correct 288 ms 23128 KB Output is correct
52 Correct 638 ms 23384 KB Output is correct
53 Correct 621 ms 23384 KB Output is correct
54 Correct 651 ms 23384 KB Output is correct
55 Correct 629 ms 29236 KB Output is correct
56 Correct 674 ms 29264 KB Output is correct
57 Correct 740 ms 29260 KB Output is correct
58 Correct 552 ms 29260 KB Output is correct
59 Correct 624 ms 35664 KB Output is correct
60 Correct 646 ms 35660 KB Output is correct
61 Correct 490 ms 23128 KB Output is correct
62 Correct 662 ms 23384 KB Output is correct
63 Correct 667 ms 23384 KB Output is correct
64 Correct 623 ms 23384 KB Output is correct
65 Correct 686 ms 23380 KB Output is correct
66 Correct 624 ms 23384 KB Output is correct
67 Correct 669 ms 23384 KB Output is correct
68 Correct 634 ms 23384 KB Output is correct
69 Correct 614 ms 23384 KB Output is correct
70 Correct 656 ms 23384 KB Output is correct
71 Correct 585 ms 23892 KB Output is correct
72 Correct 588 ms 23384 KB Output is correct
73 Correct 590 ms 23384 KB Output is correct
74 Correct 647 ms 23384 KB Output is correct
75 Correct 644 ms 23128 KB Output is correct
76 Correct 625 ms 23700 KB Output is correct
77 Correct 598 ms 23896 KB Output is correct
78 Correct 611 ms 23896 KB Output is correct
79 Correct 601 ms 23384 KB Output is correct
80 Correct 650 ms 23128 KB Output is correct
81 Correct 586 ms 23128 KB Output is correct
82 Correct 531 ms 23128 KB Output is correct
83 Correct 282 ms 23128 KB Output is correct
84 Correct 602 ms 23384 KB Output is correct
85 Correct 499 ms 23384 KB Output is correct
86 Correct 560 ms 23384 KB Output is correct
87 Correct 4 ms 23128 KB Output is correct
88 Correct 353 ms 29008 KB Output is correct
89 Correct 646 ms 27188 KB Output is correct
90 Correct 629 ms 27340 KB Output is correct
91 Correct 590 ms 30028 KB Output is correct
92 Correct 637 ms 29876 KB Output is correct
93 Correct 738 ms 29872 KB Output is correct
94 Correct 753 ms 30032 KB Output is correct
95 Correct 689 ms 30032 KB Output is correct
96 Correct 634 ms 26316 KB Output is correct
97 Correct 635 ms 26316 KB Output is correct
98 Correct 653 ms 33112 KB Output is correct
99 Correct 701 ms 29264 KB Output is correct
100 Correct 703 ms 28504 KB Output is correct
101 Correct 714 ms 27708 KB Output is correct
102 Correct 696 ms 26456 KB Output is correct
103 Correct 775 ms 35540 KB Output is correct
104 Correct 588 ms 36464 KB Output is correct
105 Correct 597 ms 36552 KB Output is correct
106 Correct 562 ms 28612 KB Output is correct
107 Correct 628 ms 26476 KB Output is correct
108 Correct 628 ms 26968 KB Output is correct
109 Correct 560 ms 26568 KB Output is correct