Submission #1247474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247474		m5588ohammed	Digital Circuit (IOI22_circuit)	C++20	4 / 100	283 ms	12292 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define mod 1000002022
#define ll long long
ll n,m;
ll to[200005],tf[200005],ta[200005],cs[200005];
vector <ll> v[200005];
void update_node(ll i){
	if(n<i) return;
	to[i]=(to[i*2]*to[i*2+1]*2)%mod;
	to[i]+=(tf[i*2]*to[i*2+1])%mod;
	to[i]%=mod;
	to[i]+=(to[i*2]*tf[i*2+1])%mod;
	to[i]%=mod;
	tf[i]=(ta[i]-to[i]+mod)%mod;
	//cout<<"UPDATE "<<i<<" "<<tf[i]<<" "<<to[i]<<endl;
	return;
}
// void flip(ll l1,ll r1,ll i,ll l,ll r){
// 	//cout<<"RANGE "<<l1<<" "<<r1<<" "<<l<<" "<<r<<" "<<i<<endl;
// 	if(l1>r||l>r1) return;
// 	if(l<=l1&&r1<=r){
// 		//cout<<"FLIP "<<i<<" "<<to[i]<<" "<<tf[i]<<endl;
// 		swap(to[i],tf[i]);
// 		return;
// 	}
// 	flip(l1,(l1+r1)/2,i*2,l,r);
// 	flip((l1+r1)/2+1,r1,i*2+1,l,r);
// 	update_node(i);
// 	return;
// }
void build(ll i){
	ta[i]=1;
	if(n<i) return;
	for(ll j:v[i]){
		build(j);
		ta[i]=(ta[i]*ta[j])%mod;
	}
	ta[i]*=(ll)v[i].size();
	ta[i]%=mod;
	//cout<<i<<" "<<ta[i]<<" "<<v[i].size()<<endl;
	return;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
	n=N;m=M;
	for(int i=0;i<m;i++) cs[i+n+1]=A[i];
	for(int i=1;i<n+m;i++) v[P[i]+1].push_back(i+1);
	build(1);
	for(int i=n+1;i<=n+m;i++){
		if(cs[i]==1) to[i]=1;
		else tf[i]=1;
	}
	for(int i=n;i>=1;i--) update_node(i);
	return;
}

int count_ways(int L, int R){
	//flip(0,n,1,L-n+1,R-n+1);
	L++;
	to[L]^=1;
	tf[L]^=1;
	L/=2;
	while(L!=0){
		update_node(L);
		L/=2;
	}
	return to[1];
}
// 3 4 3
// -1 0 1 2 1 1 0
// 1 0 1 0
// 3 4
// 4 5
// 3 6


// 1 7 3
// -1 0 0 0 0 0 0 0
// 1 1 1 1 1 1 1
// 1 1
// 2 2
// 4 7

// 3 4 1
// -1 0 0 1 1 2 2
// 1 1 1 1
// 3 3

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11