제출 #802184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802184		MadokaMagicaFan	디지털 회로 (IOI22_circuit)	C++17	100 / 100	990 ms	24000 KiB

circuit

#include "bits/stdc++.h"
#include "circuit.h"
using namespace std;
using ll = long long;
#define sz(v) ((int)(v).size())
#define pb push_back

const int N = 1e5;

ll md = 1e9+2022;
ll ans;
vector<int> adj[N+5];
vector<ll> t, st, c;
int n, m;

struct aint_lenes {
	int n;
	vector<ll> f;
	vector<int> lz;

	aint_lenes(int _n, vector<int> &a) {
		n = _n;
		f.assign(4*n, 0);
		lz.assign(4*n, 0);
		build(1, 0, n-1, a);
	}

	void build(int i, int l, int r, vector<int> &a) {
		if (l == r) {
			f[i] = a[l] % md;
			return;
		}
		int m = (l + r) >> 1;
		build(i<<1, l, m, a);
		build(i<<1|1, m+1, r, a);
		f[i] = (f[i<<1] + f[i<<1|1]) % md;
	}

	ll qry(int l, int r) {
		setl(1, 0, n-1, l, r);
		return qry(1, 0, n-1, l, r);
	}

	void setl(int i, int l, int r, int tl, int tr) {
		if (r < tl || l > tr) return;
		if (tl <= l && r <= tr) {
			lz[i] ^= 1;
			return;
		}

		int m = (l+r)>>1;
		setl(i<<1, l, m, tl, tr);
		setl(i<<1|1, m+1, r, tl, tr);

		f[i] = 0ll;
		if (lz[i<<1])
			f[i] = md - f[i<<1];
		else
			f[i] = f[i<<1];

		if (lz[i<<1|1])
			f[i] = f[i] + md - f[i<<1|1];
		else
			f[i] = f[i] + f[i<<1|1];
		f[i] %= md;
	}

	ll qry(int i, int l, int r, int tl, int tr) {
		if (r < tl || l > tr) return 0ll;
		if (lz[i]) {
			lz[i] = 0;
			f[i] = (md-f[i])%md;
			if (l != r) {
				lz[i<<1] ^= 1;
				lz[i<<1|1] ^= 1;
			}
		}
		if (tl <= l && r <= tr)
			return f[i];

		int m = (l+r) >> 1;
		return (qry(i<<1, l, m, tl, tr) +
				qry(i<<1|1, m+1, r, tl, tr)) % md;
	}
};

aint_lenes *tr;

void
dfs1(int x) {
	if (x >= n) return;

	st[x] = 0;
	t[x] = sz(adj[x]);
	for (auto u : adj[x]) {
		dfs1(u);
		st[x] = (st[x] + t[u]) % md;
		t[x] = (t[x] * t[u]) % md;
	}
}

void
dfs2(int x, ll v) {
	if (x>=n) {
		c[x-n] = (c[x-n]*v) % md;
		return;
	}

	for (auto u : adj[x]) {
		dfs2(u, v);
		v = (v * t[u]) % md;
	}
}

void
init(int _n, int _m, vector<int> p, vector<int> a)
{
	n = _n; m = _m;
	t.assign(n+m, 1);
	st.assign(n+m, 1);
	c.assign(m, 1);
	for (int i = 1; i < n+m; ++i) {
		adj[p[i]].pb(i);
	}

	dfs1(0);
	dfs2(0, 1ll);
	for (int i = 0; i < n; ++i)
		reverse(adj[i].begin(), adj[i].end());
	dfs2(0, 1ll);

	vector<int> chn(m);

	for (int i = 0; i < m; ++i) {
		if (a[i]) {
			ans = (ans + c[i]) % md;
			chn[i] = c[i];
		} else {
			chn[i] = (md - c[i]) % md;
		}
	}

	tr = new aint_lenes(m, chn);
}

int
count_ways(int l, int r)
{
	l -= n; r -= n;
	ans = (ans + tr->qry(l, r)) % md;
	return ans;
}

• 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