Submission #1172937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172937		thelegendary08	Digital Circuit (IOI22_circuit)	C++17	100 / 100	440 ms	68920 KiB

circuit

#include "circuit.h"
 //#include<stub.cpp>
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define f0r(i,n) for(int i = 0;  i< n; i++)
#define mp make_pair
using namespace std;
vector<signed> par;
vector<signed> state;
vector<vi> adj;
int n,m;
const int mod = 1e9 + 2022;
const int mxn = 2e5 + 5;
vi dep(mxn);
vi cont(mxn);
vi chil(mxn);
int binexp(int a, int b){
	int ret = 1;
	f0r(i, 30){
		if(b & (1 << i)){
			ret *= a;
			ret %= mod;
		}
		a *= a;
		a %= mod;
	}
	return ret;
}
vi tl(mxn * 2);
vi tr(mxn * 2);
vi tree(mxn * 2);
vi totcont(mxn * 2);
vi prod(mxn);

void build(int v, int l, int r){
	tl[v] = l;
	tr[v] = r;
	if(l == r){
		tree[v] = state[l] * cont[l];
		totcont[v] = cont[l];
	}
	else{
		int mid = (l + r) / 2;
		build(v * 2, l, mid);
		build(v*2+1, mid+1, r);
		tree[v] = tree[v*2] + tree[v*2+1];
		tree[v] %= mod;
		totcont[v] = totcont[v*2] + totcont[v*2+1];
		totcont[v] %= mod;
	}
}
vi la(mxn * 2);
void pull(int v){
	tree[v] = tree[v*2] + tree[v*2+1];
	tree[v] %= mod;
}
void toggle(int v){
	la[v] = 1 - la[v];
	tree[v] = totcont[v] - tree[v];
	tree[v] %= mod;
	if(tree[v] < 0){
		tree[v] += mod;
	}
}
void push(int v){
	if(la[v]){
		toggle(v*2);
		toggle(v*2+1);
		la[v] = 0;
	}
	
}
void update(int v, int l, int r){
	// cout<<"UPDATE "<<v<<'\n';
	if(tl[v] > r || tr[v] < l){
		return;
	}
	if(tl[v] >= l && tr[v] <= r){
		// cout<<"INRANGW "<<v<<'\n';
		// cout<<tree[v]<<'\n';
		toggle(v);
		// cout<<tree[v]<<'\n';
	}
	else{
		push(v);
		update(v*2, l, r);
		update(v*2+1, l, r);
		pull(v);
	}
}
int dfs(int node, int from){
	int p = chil[node];
	for(auto u : adj[node]){
		if(u != from && u < n){
			p *= dfs(u, node);
			p %= mod;
		}
	}
	prod[node] = p;
	return p;
}
void compcont(int node, int from, int cur){
	if(node >= n){
		cont[node - n] = cur;
		return;
	}
	vi pref(chil[node]);
	vi suf(chil[node]);
	vi prods;
	for(auto u : adj[node]){
		if(u != from){
			prods.pb(prod[u]);
		}
	}
	// vout(prods);
	pref[0] = prods[0];
	FOR(i, 1, chil[node]){
		pref[i] = pref[i-1] * prods[i];
		pref[i] %= mod;
	}
	suf[chil[node] - 1] = prods.back();
	for(int i = chil[node] - 2; i>=0; i--){
		suf[i] = suf[i+1] * prods[i];
		suf[i] %= mod;
	}
	// vout(pref);
	// vout(suf);
	int cnt = 0;
	for(auto u : adj[node]){
		if(u != from){
			int cc = cur;
			if(cnt != 0){
				cc *= pref[cnt - 1];
				cc %= mod;
			}
			if(cnt != suf.size() - 1){
				cc *= suf[cnt + 1];
				cc %= mod;
			}
			// cout<<cc<<'\n';
			compcont(u, node, cc);
			cnt++;
		}
	}
}
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
	n = N; m = M; par = P; state = A;
	adj.resize(n + m);
	FOR(i, 1, n+m){
		adj[P[i]].pb(i);
		chil[P[i]]++;
	}
	dfs(0, -1);
	for(int i = n; i<n+m; i++)prod[i] = 1;
	// f0r(i,n+m)cout<<prod[i]<<' ';
	  // cout<<'\n';
	 compcont(0, -1, 1);
	 // f0r(i,m)cout<<cont[i]<<' ';
	 // cout<<'\n';
	build(1, 0, m-1);
}

signed count_ways(signed l, signed r) {
	l -= n; r -= n;
	update(1, l, r);
	return 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