Submission #1077536

#TimeUsernameProblemLanguageResultExecution timeMemory
1077536Faisal_SaqibDigital Circuit (IOI22_circuit)C++17
0 / 100
639 ms10704 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const ll NP=2e5+100,mod=1000002022; ll n,m,p[NP],a[NP]; vector<ll> ma[NP]; ll dp[NP][2],lazy[NP],dp1[NP][2],lc[NP],rc[NP]; void compute(int x=0,bool continue_=1) { dp[x][0]=dp[x][1]=0; dp1[x][0]=dp1[x][1]=0; if(n<=x){ dp[x][a[x-n]]=1; dp1[x][1-a[x-n]]=1; return; } int sz=ma[x].size(); vector<int> tmp(sz+1); // DP 1 tmp[0]=1; for(auto y:ma[x]) { if(continue_) compute(y); for(int j=sz;j>=0;j--) { if(j==0) { tmp[j]=(tmp[j]*dp[y][0])%mod; } else { tmp[j]=(tmp[j]*dp[y][0])%mod; tmp[j]=(tmp[j] + ((tmp[j-1]*dp[y][1])%mod))%mod; } } } int sm=0; for(int j=sz;j>=1;j--) { sm = ( sm + tmp[j] ) % mod; dp[x][1] = ( dp[x][1] + sm ) % mod; } sm=tmp[0]; for(int j=1;j<=sz;j++) { dp[x][0] = ( dp[x][0] + sm ) % mod; sm = ( sm + tmp[j] ) % mod; } // Dp 1 for(int j=0;j<=sz;j++)tmp[j]=0; tmp[0]=1; for(auto y:ma[x]) { for(int j=sz;j>=0;j--) { if(j==0) { tmp[j]=(tmp[j]*dp1[y][0])%mod; } else { tmp[j]=(tmp[j]*dp1[y][0])%mod; tmp[j]=(tmp[j] + ((tmp[j-1]*dp1[y][1])%mod))%mod; } } } sm=0; for(int j=sz;j>=1;j--) { sm = ( sm + tmp[j] ) % mod; dp1[x][1] = ( dp1[x][1] + sm ) % mod; } sm=tmp[0]; for(int j=1;j<=sz;j++) { dp1[x][0] = ( dp1[x][0] + sm ) % mod; sm = ( sm + tmp[j] ) % mod; } } void prepro(int x=0){ if(n<=x) { lc[x]=rc[x]=-1; return; } lc[x]=ma[x][0]; rc[x]=ma[x][1]; prepro(lc[x]); prepro(rc[x]); } void push(int v) { if(!lazy[v])return; lazy[lc[v]]^=lazy[v]; lazy[rc[v]]^=lazy[v]; swap(dp[v][0],dp1[v][0]); swap(dp[v][1],dp1[v][1]); lazy[v]=0; } void update(int v,int l,int r,int ql,int qr) { push(v); if(qr<l or r<ql) // nothing changes here return; if(ql<=l and r<=qr) // whole subtree to be updated { lazy[v]^=1; return; } push(v); int mid=(l+r)/2; update(lc[v],l,mid,ql,qr); update(rc[v],mid+1,r,ql,qr); compute(v,0); } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N,m=M; for(ll i=0;i<n+m;i++) { p[i]=P[i]; if(p[i]!=-1)ma[p[i]].push_back(i); } for(ll j=0;j<m;j++)a[j]=A[j]; prepro(); compute(); } int count_ways(int L, int R) { for(ll i=L-n;i<=R-n;i++)a[i]=(a[i]?0:1); update(0,0,m-1,L-n,R-n); push(1); return (int)dp[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...