Submission #642860

#	Time	Username	Problem	Language	Result	Execution time	Memory
642860		dykw	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1158 ms	42612 KiB

circuit

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 5, MOD = 1000002022;

int n, m, s[N];
i64 w[N], f[N], wp[N];
std::vector<int> g[N];

void calc_sum(int u) {
	if (u > n) return w[u] = 1, void();
	w[u] = g[u].size();
	for (int v : g[u]) calc_sum(v), w[u] = w[u]*w[v]%MOD;
}

void calc_coef(int u) {
	if (u > n) return;
	std::vector<i64> pre(g[u].size() + 2), suf(g[u].size() + 2);
	pre[0] = suf[g[u].size()+1] = 1;
	for (int i = 1; i <= int(g[u].size()); ++i) pre[i] = pre[i-1]*w[g[u][i-1]]%MOD;
	for (int i = int(g[u].size()); i >= 1; --i) suf[i] = suf[i+1]*w[g[u][i-1]]%MOD;
	for (int i = 0; i < int(g[u].size()); ++i)
		wp[g[u][i]] = wp[u]*pre[i]%MOD*suf[i+2]%MOD, calc_coef(g[u][i]);
}

#define ls(x) (x*2)
#define rs(x) (x*2+1)

struct {
	int l, r, ans0, ans1;
	bool tag;
} tr[N*4];

void pushup(int x) {
	tr[x].ans0 = (tr[ls(x)].ans0+tr[rs(x)].ans0)%MOD;
	tr[x].ans1 = (tr[ls(x)].ans1+tr[rs(x)].ans1)%MOD;
}

void build(int l, int r, int x = 1) {
	tr[x] = {l, r, 0, 0, false};
	if (l == r) {
		if (s[l]) tr[x].ans1 = wp[l+n];
		else tr[x].ans0 = wp[l+n];
		return;
	}
	int mid = (l+r)/2;
	build(l, mid, ls(x)), build(mid+1, r, rs(x));
	pushup(x);
}

void update(int x) {
	std::swap(tr[x].ans0, tr[x].ans1);
	tr[x].tag ^= 1;
}

void pushdown(int x) {
	if (tr[x].tag) {
		update(ls(x)), update(rs(x));
		tr[x].tag = false;
	}
}

void flip(int l, int r, int x = 1) {
	if (l <= tr[x].l && tr[x].r <= r) return update(x);
	pushdown(x);
	int mid = (tr[x].l+tr[x].r)/2;
	if (l <= mid) flip(l, r, ls(x));
	if (r > mid) flip(l, r, rs(x));
	pushup(x);
}

#undef ls
#undef rs

void init(int n, int m, std::vector<int> p, std::vector<int> a) {
	::n = n, ::m = m;
	for (int i = 1; i <= m; ++i) s[i] = a[i-1];
	for (int i = 1; i < n+m; ++i) g[p[i]+1].push_back(i+1);
	calc_sum(1);
	wp[1] = 1, calc_coef(1);
	build(1, m);
}

int count_ways(int l, int r) {
	flip(l-n+1, r-n+1);
	return tr[1].ans1;
}

• 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