Submission #1078718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078718		Gromp15	Digital Circuit (IOI22_circuit)	C++17	100 / 100	782 ms	15560 KiB

circuit

#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)x.size()
#define ar array
#include "circuit.h"
using namespace std;

const int mod = int(1e9) + 2022;
void fadd(int &a, int b) {
	a += b;
	if (a >= mod) a -= mod;
}
int add(int x, int y) {
	return x+y >= mod ? x+y-mod : x+y;
}


struct seg {
	int N; vector<int> tree, tot, lazy;
	seg() {}
	seg(int n, const vector<int>& v, const vector<int>& a) : N(1<<(__lg(n)+1)), tree(2*N), tot(2*N), lazy(2*N) {
		for (int i = 0; i < n; i++) tot[i+N] = v[i], tree[i+N] = v[i] * a[i];
		for (int i = N-1; i >= 1; i--) tot[i] = add(tot[i*2], tot[i*2+1]), tree[i] = add(tree[i*2], tree[i*2+1]);
	}
	void push(int node) {
		if (!lazy[node]) return;
		tree[node] = tot[node] - tree[node];
		if (tree[node] < 0) tree[node] += mod;
		if (node < N) {
			lazy[node*2] ^= 1;
			lazy[node*2+1] ^= 1;
		}
		lazy[node] = 0;
	}
	void update(int node, int nl, int nr, int ql, int qr) {
		push(node);
		if (ql > nr || qr < nl) return;
		if (ql <= nl && nr <= qr) {
			lazy[node] ^= 1; push(node); return;
		}
		int mid = (nl+nr)/2;
		update(node*2, nl, mid, ql, qr);
		update(node*2+1, mid+1, nr, ql, qr);
		tree[node] = add(tree[node*2], tree[node*2+1]);
	}
} st;

vector<int> p, a, sub, sub2, val;
vector<vector<int>> adj;
int n, m;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n = N, m = M;
	p = P, a = A;
	adj.resize(N), sub.resize(N+M, 1), sub2.resize(N+M, 1);
	for (int i = 1; i < N + M; i++) adj[P[i]].emplace_back(i);
	for (int i = N-1; i >= 0; i--) {
		sub[i] = sz(adj[i]);
		int cur = sz(adj[i]);
		vector<int> pref(cur), suff(cur);
		for (int j = 0; j < cur; j++) {
			pref[j] = suff[j] = sub[adj[i][j]];
		}
		for (int j = 1; j < cur; j++) pref[j] = (ll)pref[j-1] * pref[j] % mod;
		for (int j = cur-2; j >= 0; j--) suff[j] = (ll)suff[j+1] * suff[j] % mod;
		for (int j = 0; j < cur; j++) {
			int u = adj[i][j];
			sub[i] = (ll)sub[i] * sub[u] % mod;
			sub2[u] = (ll)(j ? pref[j-1] : 1) * (j+1 < cur ? suff[j+1] : 1) % mod;
		}
	}
	val.resize(N+M);
	val[0] = 1;
	for (int i = 1; i < N + M; i++) val[i] = (ll)val[p[i]] * sub2[i] % mod;
	vector<int> val2(M);
	for (int i = N; i < N+M; i++) val2[i-N] = val[i];
	st = seg(m, val2, A);
}


int count_ways(int L, int R) {
	st.update(1, 0, st.N-1, L - n, R - n);
	return st.tree[1];
}

• 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