Submission #1172868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172868		thelegendary08	Digital Circuit (IOI22_circuit)	C++17	52 / 100	411 ms	35272 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);
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);
void dfs(int node, int from){
	for(auto u : adj[node]){
		if(u != from){
			dep[u] = 1 + dep[node];
			dfs(u, node);
		}
	}
}
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);
	}
}
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);
	}
	dfs(0, -1);
	f0r(i, m){
		cont[i] = binexp(2, n - dep[i + 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: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11