Submission #1063681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063681		Arapak	Digital Circuit (IOI22_circuit)	C++17	100 / 100	786 ms	30936 KiB

circuit

#include "circuit.h"
#include "bits/stdc++.h"

using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;

#ifdef DEBUG
auto& operator<<(auto& os, pair<auto, auto> &p) {
	return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto& os, const auto &v) {
	os<<"{";
	for(auto it=begin(v);it!=end(v);++it) {
		if(it != begin(v)) os<<", ";
		os<<(*it);
	}
	return os<<"}";
}

void dbg_out(auto... x) {
	((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

const ll mod = 1000002022;

struct SegTree {
	int base;
	vector<ll> tree, inv;
	vector<bool> lazy;
	void merge(int v) {
		tree[v] = (tree[v*2] + tree[v*2+1]) % mod;
		inv[v] = (inv[v*2] + inv[v*2+1]) % mod;
	}

	void build(int v, int l, int r, const vector<ll> &vals, const vector<int> &a) {
		if(l+1 == r) {
			tree[v] = l < sz(vals) ? vals[l] : 0;
			if(l < sz(vals) && !a[l]) swap(tree[v], inv[v]);
			return;
		}
		int mid = (l + r) / 2;
		build(v*2, l, mid, vals, a);
		build(v*2+1, mid, r, vals, a);
		merge(v);
	}

	SegTree(const vector<ll> &vals, const vector<int> &a) {
		// base = bit_ceil(uint(vals.size()));
		base = 1;
		while(base < sz(vals))
			base *= 2;
		dbg(base);
		tree.assign(2*base, 0);
		inv.assign(2*base, 0);
		lazy.assign(2*base, 0);
		build(1, 0, base, vals, a);
	}

	void push(int v) {
		if(lazy[v]) {
			swap(tree[v*2], inv[v*2]);
			lazy[v*2] = !lazy[v*2];
			swap(tree[v*2+1], inv[v*2+1]);
			lazy[v*2+1] = !lazy[v*2+1];
			lazy[v] = false;
		}
	}

	void update(int v, int l, int r, int a, int b) {
		if(r <= a || b <= l) return;
		if(a <= l && r <= b) {
			swap(tree[v], inv[v]);
			lazy[v] = !lazy[v];
			return;
		}
		push(v);
		int mid = (l + r) / 2;
		update(v*2, l, mid, a, b);
		update(v*2+1, mid, r, a, b);
		merge(v);
	}
};

int n, m;
vi p, a;
vector<vi> g;

vector<ll> mult;
void dfs_mult(int v) {
	if(v >= n) return;
	dbg(v, g[v]);
	mult[v] = ll(sz(g[v]));
	for(auto e : g[v]) {
		dfs_mult(e);
		if(e < n)
			mult[v] = mult[v] * mult[e] % mod;
	}
}

vector<ll> weight;
void dfs(int v, ll w) {
	if(v >= n) {
		weight[v - n] = w;
		return;
	}
	dbg(v, w);
	vector<ll> pref(sz(g[v]) + 1, 1), suff(sz(g[v]) + 1, 1);
	rep(i,0,sz(g[v])) {
		pref[i+1] = (pref[i] * mult[g[v][i]]) % mod;
		suff[i+1] = (suff[i] * mult[g[v][sz(g[v]) -i-1]]) % mod;
	}
	dbg(pref, suff);

	rep(i,0,sz(g[v])) {
		ll we = pref[i] * suff[sz(g[v]) - i - 1] % mod;
		dfs(g[v][i], w * we % mod);
	}
}

SegTree *tree;

void init(int N, int M, vi P, vi A) {
	n = N; m = M; p = P; a = A;
	g.resize(n);
	rep(i,1,n+m)
		g[p[i]].push_back(i);
	mult.assign(n+m, 1);
	dfs_mult(0);
	dbg(mult);
	weight.resize(m);
	dfs(0, 1);
	dbg(weight);
	tree = new SegTree(weight, a);
}

int count_ways(int L, int R) {
	tree->update(1,0,tree->base,L-n,R-n+1);
	dbg(tree->tree);
	dbg(tree->inv);
	dbg(tree->lazy);
	return (int)tree->tree[1];

	// rep(i,L-n,R-n+1)
	// 	a[i] = !a[i];

	// ll res = 0;
	// rep(i,0,m)
	// 	if(a[i]) res = (res + weight[i]) % mod;

	// return (int)res;
}

• 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