Submission #1067087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067087		pavement	Digital Circuit (IOI22_circuit)	C++17	100 / 100	894 ms	38360 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

using ll = long long;

const int MOD = (int)1e9 + 2022;
int N, M, coeff[100005];
vector<int> A, adj[200005];

struct node {
	node *left, *right;
	int S, E, val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			val = adj[S].size();
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = (ll)left->val * right->val % MOD;
	}
	void upd(int p, int v) {
		if (S == E) {
			val = v;
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->upd(p, v);
		} else {
			right->upd(p, v);
		}
		val = (ll)left->val * right->val % MOD;
	}
} *root;

struct node2 {
	node2 *left, *right;
	int S, E, val[2];
	bool ip;
	node2(int _s, int _e) : S(_s), E(_e), ip(0) {
		if (S == E) {
			val[A[S]] = coeff[S];
			val[!A[S]] = 0;
			return;
		}
		int M = (S + E) / 2;
		left = new node2(S, M);
		right = new node2(M + 1, E);
		val[0] = (left->val[0] + right->val[0]) % MOD;
		val[1] = (left->val[1] + right->val[1]) % MOD;
	}
	void prop() {
		if (S == E || !ip) {
			return;
		}
		swap(left->val[0], left->val[1]);
		swap(right->val[0], right->val[1]);
		left->ip ^= 1;
		right->ip ^= 1;
		ip = 0;
	}
	void upd(int l, int r) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			swap(val[0], val[1]);
			ip ^= 1;
			return;
		}
		prop();
		left->upd(l, r);
		right->upd(l, r);
		val[0] = (left->val[0] + right->val[0]) % MOD;
		val[1] = (left->val[1] + right->val[1]) % MOD;
	}
} *root2;

void dfs(int u) {
	if (u < N) {
		root->upd(u, 1);
	} else {
		coeff[u - N] = root->val;
	}
	for (auto v : adj[u]) {
		dfs(v);
	}
	if (u < N) {
		root->upd(u, adj[u].size());
	}
}

void init(int N, int M, vector<int> P, vector<int> A) {
	::N = N;
	::M = M;
	::A = A;
	for (int i = 0; i < N + M; i++) {
		adj[P[i]].pb(i);
	}
	root = new node(0, N - 1);
	dfs(0);
	root2 = new node2(0, M - 1);
}

int count_ways(int L, int R) {
	root2->upd(L - N, R - N);
	return root2->val[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