| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1077519 | Faisal_Saqib | Digital Circuit (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define CAL(x) dp[x][1]=(2*(dp[2*v+1][1]*dp[2*v+1][1])%mod)+(((dp[2*v+1][1]*dp[2*v+1][0])+(dp[2*v+1][0]*dp[2*v+1][1]))%mod);dp[x][1]%=mod;dp[x][0]=(((dp[2*v+1][1]*dp[2*v+1][0])+(dp[2*v+1][0]*dp[2*v+1][1]))%mod) + (((dp[2*v+1][0]*dp[2*v+1][0])*2)%mod);dp[x][0]%=mod;dp1[x][1]=(2*(dp1[2*v+1][1]*dp1[2*v+1][1])%mod)+(((dp1[2*v+1][1]*dp1[2*v+1][0])+(dp1[2*v+1][0]*dp1[2*v+1][1]))%mod);dp1[x][1]%=mod;dp1[x][0]=(((dp1[2*v+1][1]*dp1[2*v+1][0])+(dp1[2*v+1][0]*dp1[2*v+1][1]))%mod) + (((dp1[2*v+1][0]*dp1[2*v+1][0])*2)%mod);dp1[x][0]%=mod;
const ll NP=2e5+100,mod=1e9+2022;
ll n,m,p[NP],a[NP];
ll dp[NP][2],lazy[NP],dp1[NP][2],l[NP],r[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;
}
compute(2*v+1);
compute(2*v+2);
CAL(x)
// dp[x][1]=(2*(dp[2*v+1][1]*dp[2*v+1][1])%mod)+(((dp[2*v+1][1]*dp[2*v+1][0])+(dp[2*v+1][0]*dp[2*v+1][1]))%mod);dp[x][1]%=mod;dp[x][0]=(((dp[2*v+1][1]*dp[2*v+1][0])+(dp[2*v+1][0]*dp[2*v+1][1]))%mod) + (((dp[2*v+1][0]*dp[2*v+1][0])*2)%mod);dp[x][0]%=mod;dp1[x][1]=(2*(dp1[2*v+1][1]*dp1[2*v+1][1])%mod)+(((dp1[2*v+1][1]*dp1[2*v+1][0])+(dp1[2*v+1][0]*dp1[2*v+1][1]))%mod);dp1[x][1]%=mod;dp1[x][0]=(((dp1[2*v+1][1]*dp1[2*v+1][0])+(dp1[2*v+1][0]*dp1[2*v+1][1]))%mod) + (((dp1[2*v+1][0]*dp1[2*v+1][0])*2)%mod);dp1[x][0]%=mod;
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)
{
l[x]=r[x]=x-n;
return;
}
prepro(2*x+1);
prepro(2*x+2);
l[x]=l[2*x+1];
r[x]=r[2*x+2];
}
void push(int v)
{
if(!lazy[v])return;
lazy[lc[v]]^=lazy[v];
lazy[rc[v]]^=lazy[v];
swap(dp[lc[v]][0],dp1[lc[v]][0]);
swap(dp[rc[v]][1],dp1[rc[v]][1]);
}
void update(int v,int&ql,int&qr)
{
if(qr<l[v] or r[v]<ql) // nothing changes here
return;
if(ql<=l[v] and r[v]<=qr) // whole subtree to be updated
{
swap(dp[v][0],dp1[v][0]);
swap(dp[v][1],dp1[v][1]);
lazy[v]^=1;
return;
}
push(v);
update(2*v + 1,ql,qr);
update(2*v + 2,ql,qr);
CAL(v)
}
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)
{
L-=n,R-=n;
update(0,L,R);
return (int)dp[0][1];
}