Submission #930196

#	Time	Username	Problem	Language	Result	Execution time	Memory
930196		Edu175	Digital Circuit (IOI22_circuit)	C++17	34 / 100	3088 ms	39832 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define dfore(i,a,b) for(ll i=b-1,ioi=a;i>=ioi;i--)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto djfhg:v)cout<<djfhg<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=2e5+5,MOD=1000002022;
int add(int a, int b){a+=b;if(a>=MOD)a-=MOD;return a;}
int sub(int a, int b){a-=b;if(a<0)a+=MOD;return a;}
int mul(ll a, ll b){return a*b%MOD;}

ll n,m;
vector<ll>g[MAXN];
ll a[MAXN],tot[MAXN],dp[MAXN];
vector<ll> pre[MAXN], suf[MAXN];
struct tn{
	ll r0,r1;
};
/*string cv(tn a){
	return "["+to_string(a.r0)+","+to_string(a.r1)+"]";
}*/
tn unit(ll v){
	if(!v)return tn({1,0});
	return tn({0,1});
}
typedef ll tl;
tl CLEAR=0;
tn NEUT({0,0});
tn oper(tn a, tn b, ll k){
	tn c=NEUT;
	ll xa=2*k-1,xb=2*k;
	c.r0=add(mul(a.r0,tot[xb]),mul(b.r0,tot[xa]));
	c.r1=add(mul(a.r1,tot[xb]),mul(b.r1,tot[xa]));
	return c;
}
void acum(tl &a, ll v){
	a^=v;
};
void calc(tn &a, ll v){
	if(v)swap(a.r0,a.r1);
}
struct STree{
	vector<tn>st; vector<tl>lazy; ll n;
	STree(ll n): st(4*n+5,NEUT),lazy(4*n+5,CLEAR),n(n){}
	void push(ll k, ll s, ll e){
		calc(st[k],lazy[k]);
		if(e-s>1){
			acum(lazy[2*k],lazy[k]);
			acum(lazy[2*k+1],lazy[k]);
		}
		lazy[k]=CLEAR;
	}
	void init(ll k, ll s, ll e, vector<int>&a){
		if(e-s==1)st[k]=unit(a[s]);
		else {
			ll m=(s+e)/2;
			init(2*k,s,m,a); init(2*k+1,m,e,a);
			st[k]=oper(st[2*k],st[2*k+1],k);
		}
		//cout<<"init "<<k<<" "<<s<<","<<e<<" = "<<cv(st[k])<<"\n";
	}
	void upd(ll k, ll s, ll e, ll a, ll b){
		push(k,s,e);
		if(e<=a||b<=s);
		else if(a<=s&&e<=b){
			acum(lazy[k],1);
			push(k,s,e);
		}
		else {
			ll m=(s+e)/2;
			upd(2*k,s,m,a,b); upd(2*k+1,m,e,a,b);
			st[k]=oper(st[2*k],st[2*k+1],k);
		}
		//cout<<"upd "<<k<<" "<<s<<","<<e<<" "<<a<<","<<b<<" = "<<cv(st[k])<<"\n";
	}
	void init(vector<int>&a){init(1,0,n,a);}
	void upd(ll a, ll b){upd(1,0,n,a,b);}
	ll get(){
		push(1,0,n);
		return st[1].r1;
	}
};
STree st(0);
bool segtree=1;
void init(int N, int M, std::vector<int> P, std::vector<int> A){
	n=N,m=M;
	segtree=__builtin_popcountll(m)==1&&m==n+1;
	fore(i,0,SZ(P)){
		if(P[i]!=-1)g[P[i]].pb(i);
		if(i)segtree&=P[i]==(i-1)/2;
	}
	fore(i,0,m)a[i+n]=A[i];
	fore(i,0,m)tot[n+i]=1;
	dfore(x,0,n){
		ll k=SZ(g[x]);
		tot[x]=k;
		for(auto y:g[x])tot[x]=mul(tot[x],tot[y]);
		pre[x].resize(k+1,1),suf[x].resize(k+1,1);
		fore(i,1,k+1)pre[x][i]=mul(pre[x][i-1],tot[g[x][i-1]]);
		dfore(i,0,k)suf[x][i]=mul(suf[x][i+1],tot[g[x][i]]);
	}
	st=STree(m);
	st.init(A);
	//cout<<segtree<<" seg\n";
}

int count_ways(int L, int R){
	if(segtree){
		ll l=L-n,r=R-n+1;
		//cout<<"cw "<<l<<","<<r<<":\n";
		//fore(i,1,n+m)cout<<i<<": "<<cv(st.st[i])<<"\n";
		st.upd(l,r);
		return st.get();
	}
	else {
		fore(i,L,R+1)a[i]^=1;
		//fore(i,n,n+m)cout<<a[i];;cout<<"\n";
		dfore(x,0,n+m){
			dp[x]=0;
			if(x>=n)dp[x]=a[x];
			else {
				fore(i,0,SZ(g[x])){
					auto y=g[x][i];
					dp[x]=add(dp[x],mul(dp[y],mul(pre[x][i],suf[x][i+1])));
				}
			}
			//cout<<x<<": "<<dp[x]<<"\n";
		}
	return dp[0];
	}
}

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