Submission #1060309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060309		DorostWef	Digital Circuit (IOI22_circuit)	C++17	100 / 100	775 ms	36552 KiB

circuit

#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 / 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