Submission #770853

#	Time	Username	Problem	Language	Result	Execution time	Memory
770853		josanneo22	Digital Circuit (IOI22_circuit)	C++17	100 / 100	956 ms	43720 KiB

circuit

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 1, MOD = 1e9 + 2022;
class SegmentTree {
private:
	struct node {
		int rev, sum[2];
		node() { rev = 0, sum[0] = sum[1] = 0; }
	}tree[maxn << 2];

	inline int left(int x) { return x << 1; }
	inline int right(int x) { return x << 1 | 1; }
	inline void pushup(int pos) {
		tree[pos].sum[0] = (tree[left(pos)].sum[0] + tree[right(pos)].sum[0]) % MOD;
		tree[pos].sum[1] = (tree[left(pos)].sum[1] + tree[right(pos)].sum[1]) % MOD;
	}
	inline void reverse(int pos) {
		tree[pos].rev ^= 1;
		swap(tree[pos].sum[0], tree[pos].sum[1]);
	}
	inline void pushdown(int pos) {
		if (tree[pos].rev) {
			reverse(left(pos));
			reverse(right(pos));
			tree[pos].rev = 0;
		}
	}
public:
	inline void Insert(int u, int s, int k, int l, int r, int pos) {
		tree[pos] = node();
		if (l == r) {
			tree[pos].sum[s] = k;
			return;
		}
		int mid = (l + r) >> 1;
		if (u <= mid) Insert(u, s, k, l, mid, left(pos));
		if (mid < u) Insert(u, s, k, mid + 1, r, right(pos));
		pushup(pos);
	}
	inline void Modify(int ul, int ur, int l, int r, int pos) {
		if (ul <= l && r <= ur) {
			reverse(pos);
			return;
		}
		int mid = (l + r) >> 1;
		pushdown(pos);
		if (ul <= mid) Modify(ul, ur, l, mid, left(pos));
		if (mid < ur) Modify(ul, ur, mid + 1, r, right(pos));
		pushup(pos);
	}
	inline int Query() { return tree[1].sum[1]; }
}S;

vector<int> G[maxn];
int n, m, siz[maxn], coef[maxn], prod[maxn];
inline void dfs1(int u) {
	if (!siz[u]) {
		prod[u] = 1; return;
	}
	prod[u] = siz[u];
	for (int v : G[u]) {
		dfs1(v);
		prod[u] = (ll)prod[v] * (ll)prod[u] % MOD;
	}
}
inline void dfs2(int u, int k) {
	coef[u] = k;

	if (!siz[u]) return;
	vector <int> pre(siz[u]), suf(siz[u]);

	pre[0] = prod[G[u][0]];
	for (int i = 1; i <= siz[u] - 1; ++i) pre[i] = (ll)prod[G[u][i]] * (ll)pre[i - 1] % MOD;

	suf[siz[u] - 1] = prod[G[u][siz[u] - 1]];
	for (int i = siz[u] - 2; i >= 0; --i) suf[i] = (ll)prod[G[u][i]] * (ll)suf[i + 1] % MOD;

	for (int i = 0; i < siz[u]; ++i) {
		int tmp = k;
		if (i > 0) tmp = (ll)tmp * (ll)pre[i - 1] % MOD;
		if (i < siz[u] - 1) tmp = (ll)tmp * (ll)suf[i + 1] % MOD;
		dfs2(G[u][i], tmp);
	}
}
void init(int N, int M, vector <int> P, vector <int> A) {
	n = N, m = M;
	for (int i = 1; i < n + m; ++i) G[P[i]].push_back(i);
	for (int i = 0; i < n + m; ++i) siz[i] = G[i].size();
	dfs1(0), dfs2(0, 1);
	for (int i = 0; i < m; ++i) S.Insert(i + 1, A[i], coef[n + i], 1, m, 1);
}
int count_ways(int L, int R) {
	S.Modify(L - n + 1, R - n + 1, 1, m, 1);
	return S.Query();
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11