Submission #693759

#	Time	Username	Problem	Language	Result	Execution time	Memory
693759		Pyqe	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1268 ms	48732 KiB

circuit

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

using namespace std;

const long long dv=1e9+2022;
long long n,m,pr[200069],a[100069],dp[200069],wg[100069];
vector<long long> al[200069];

struct segtree
{
	long long l,r,sm[2];
	bool iv;
	segtree *p[2];
	
	void bd(long long lh,long long rh)
	{
		l=lh;
		r=rh;
		iv=0;
		if(l==r)
		{
			sm[a[l]]=wg[l];
			sm[!a[l]]=0;
		}
		else
		{
			long long ii,md=(l+r)/2;
			
			for(ii=0;ii<2;ii++)
			{
				p[ii]=new segtree;
				p[ii]->bd(!ii?l:md+1,!ii?md:r);
			}
			for(ii=0;ii<2;ii++)
			{
				sm[ii]=(p[0]->sm[ii]+p[1]->sm[ii])%dv;
			}
		}
	}
	inline void blc()
	{
		if(iv)
		{
			long long ii;
			
			for(ii=0;ii<2;ii++)
			{
				swap(p[ii]->sm[0],p[ii]->sm[1]);
				p[ii]->iv^=1;
			}
			iv=0;
		}
	}
	void ud(long long lh,long long rh)
	{
		if(l>rh||r<lh);
		else if(l>=lh&&r<=rh)
		{
			swap(sm[0],sm[1]);
			iv^=1;
		}
		else
		{
			long long ii;
			
			blc();
			for(ii=0;ii<2;ii++)
			{
				p[ii]->ud(lh,rh);
			}
			for(ii=0;ii<2;ii++)
			{
				sm[ii]=(p[0]->sm[ii]+p[1]->sm[ii])%dv;
			}
		}
	}
}
sg;

void dfs(long long x)
{
	long long i,sz=al[x].size(),l;
	
	dp[x]=max(sz,1ll);
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		dfs(l);
		dp[x]=dp[x]*dp[l]%dv;
	}
}

void dfs2(long long x,long long cw)
{
	if(x<=n)
	{
		long long i,sz=al[x].size(),l;
		vector<long long> mla,mla2;
		
		mla.push_back(1);
		for(i=0;i<sz;i++)
		{
			l=al[x][i];
			mla.push_back(mla[i]*dp[l]%dv);
		}
		mla2.push_back(1);
		for(i=sz-1;i>=0;i--)
		{
			l=al[x][i];
			mla2.push_back(mla2[sz-1-i]*dp[l]%dv);
		}
		for(i=0;i<sz;i++)
		{
			l=al[x][i];
			dfs2(l,cw*mla[i]%dv*mla2[sz-1-i]%dv);
		}
	}
	else
	{
		wg[x-n]=cw;
	}
}

void init(int on,int om,vector<int> prr,vector<int> aa)
{
	long long i;
	
	n=on;
	m=om;
	for(i=1;i<=n+m;i++)
	{
		pr[i]=prr[i-1]+1;
	}
	for(i=1;i<=m;i++)
	{
		a[i]=aa[i-1];
	}
	for(i=2;i<=n+m;i++)
	{
		al[pr[i]].push_back(i);
	}
	dfs(1);
	dfs2(1,1);
	sg.bd(1,m);
}

int count_ways(int lb,int rb)
{
	lb++;
	rb++;
	lb-=n;
	rb-=n;
	sg.ud(lb,rb);
	return sg.sm[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