Submission #640759

#	Time	Username	Problem	Language	Result	Execution time	Memory
640759		jamezzz	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1232 ms	56604 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define maxn 200005
#define mod 1000002022

struct node{
	int s,e,m,lz,on;ll v,sm;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)>>1;lz=0;v=0;sm=0;on=0;
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		if(lz)v=(sm-v+mod)%mod;
		if(s!=e){
			l->lz^=lz;
			r->lz^=lz;
		}
		lz=0;
	}
	void set(int x,ll nv){
		if(s==x&&e==x){sm=nv;return;}
		if(x<=m)l->set(x,nv);
		else r->set(x,nv);
		l->ppo(),r->ppo();
		v=(l->v+r->v)%mod;
		sm=(l->sm+r->sm)%mod;
	}
	void flip(int x,int y){
		if(s==x&&e==y){lz^=1;return;}
		if(y<=m)l->flip(x,y);
		else if(x>m)r->flip(x,y);
		else l->flip(x,m),r->flip(m+1,y);
		l->ppo(),r->ppo();
		v=(l->v+r->v)%mod;
		sm=(l->sm+r->sm)%mod;
	}
	ll qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return l->qry(x,m),r->qry(m+1,y);
	}
}*rt;

int n,m;
ll s[maxn],c[maxn];
vector<int> AL[maxn];

void dfs(int u){
	if(u<n){
		s[u]=AL[u].size();
		for(int v:AL[u]){
			dfs(v);
			s[u]=(s[u]*s[v])%mod;
		}
	}
	else s[u]=1;
	//printf("dfs: %d %lld\n",u,s[u]);
}

void dfs2(int u,ll tot){
	//printf("dfs2: %d %lld\n",u,tot);
	if(u<n){
		vector<ll> vals;
		for(int v:AL[u])vals.push_back(s[v]);
		vector<ll> pfx={1},sfx={1};
		for(int i=0;i<vals.size();++i){
			pfx.push_back((pfx.back()*vals[i])%mod);
		}
		for(int i=vals.size()-1;i>=0;--i){
			sfx.push_back((sfx.back()*vals[i])%mod);
		}
		reverse(sfx.begin(),sfx.end());
		for(int i=0;i<vals.size();++i){
			dfs2(AL[u][i],(((tot*pfx[i])%mod)*sfx[i+1])%mod);
		}
	}
	else c[u]=tot;
}

void init(int N,int M,vector<int> P,vector<int> A){
	n=N,m=M;
	rt=new node(0,m-1);
	for(int i=1;i<n+m;++i){
		AL[P[i]].push_back(i);
	}
	dfs(0);
	dfs2(0,1);
	for(int i=0;i<m;++i){
		rt->set(i,c[i+n]);
		if(A[i])rt->flip(i,i);
	}
}

int count_ways(int L, int R){
	rt->flip(L-n,R-n);
	return (int)rt->qry(0,m-1);
}

Compilation message (stderr)

circuit.cpp: In function 'void dfs2(int, ll)':
circuit.cpp:72:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i=0;i<vals.size();++i){
      |               ~^~~~~~~~~~~~
circuit.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i=0;i<vals.size();++i){
      |               ~^~~~~~~~~~~~

• 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