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
const ll NP=2e5+100,mod=1000002022;
ll n,m,p[NP],a[NP];
vector<ll> ma[NP];
const int KP=100;
vector<ll> knapsack[NP];
ll dp[NP][2],lazy[NP],dp1[NP][2],lc[NP],rc[NP],mi[NP],mx[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;
mx[x]=x-n;
mi[x]=x-n;
return;
}
int sz=ma[x].size();
if(knapsack[x].size()==0)knapsack[x].resize(sz+2,0);
for(int j=0;j<=sz;j++)knapsack[x][j]=0;
knapsack[x][0]=1;
mx[x]=-1e9;
mi[x]=1e9;
for(auto y:ma[x])
{
if(continue_)
compute(y);
mx[x]=max(mx[x],mx[y]);
mi[x]=min(mi[x],mi[y]);
for(int j=sz;j>=0;j--)
{
if(j==0)
{
knapsack[x][j]=(knapsack[x][j]*dp[y][0])%mod;
}
else
{
knapsack[x][j]=(knapsack[x][j]*dp[y][0])%mod;
knapsack[x][j]=(knapsack[x][j] + ((knapsack[x][j-1]*dp[y][1])%mod))%mod;
}
}
}
int sm=0;
for(int j=sz;j>=1;j--)
{
sm = ( sm + knapsack[x][j] ) % mod;
dp[x][1] = ( dp[x][1] + sm ) % mod;
}
sm=knapsack[x][0];
for(int j=1;j<=sz;j++)
{
dp[x][0] = ( dp[x][0] + sm ) % mod;
sm = ( sm + knapsack[x][j] ) % mod;
}
// Dp 1
for(int j=0;j<=sz;j++)knapsack[x][j]=0;
knapsack[x][0]=1;
for(auto y:ma[x])
{
for(int j=sz;j>=0;j--)
{
if(j==0)
{
knapsack[x][j]=(knapsack[x][j]*dp1[y][0])%mod;
}
else
{
knapsack[x][j]=(knapsack[x][j]*dp1[y][0])%mod;
knapsack[x][j]=(knapsack[x][j] + ((knapsack[x][j-1]*dp1[y][1])%mod))%mod;
}
}
}
sm=0;
for(int j=sz;j>=1;j--)
{
sm = ( sm + knapsack[x][j] ) % mod;
dp1[x][1] = ( dp1[x][1] + sm ) % mod;
}
sm=knapsack[x][0];
for(int j=1;j<=sz;j++)
{
dp1[x][0] = ( dp1[x][0] + sm ) % mod;
sm = ( sm + knapsack[x][j] ) % mod;
}
}
void push(int&v)
{
if(!lazy[v])return;
for(ll&y:ma[v])
lazy[y]^=lazy[v];
swap(dp[v][0],dp1[v][0]);
swap(dp[v][1],dp1[v][1]);
lazy[v]=0;
}
void update(int v,int&ql,int&qr)
{
// // cout<<"WAnt to update "<<ql<<' '<<qr<<" At "<<v<<' '<<mi[v]<<' '<<mx[v]<<endl;
push(v);
if(qr<mi[v] or mx[v]<ql) // nothing changes here
return;
if(ql<=mi[v] and mx[v]<=qr) // whole subtree to be updated // just swap the values else
{
lazy[v]^=1;
push(v);
return;
}
int x=v;
dp[x][0]=dp[x][1]=0;
dp1[x][0]=dp1[x][1]=0;
int sz=ma[x].size();
for(int j=0;j<=sz;j++)knapsack[x][j]=0;
knapsack[x][0]=1;
for(ll&y:ma[x])
{
update(y,ql,qr);
for(int j=sz;j>=0;j--)
{
if(j==0)
{
knapsack[x][j]=(knapsack[x][j]*dp[y][0])%mod;
}
else
{
knapsack[x][j]=(knapsack[x][j]*dp[y][0])%mod;
knapsack[x][j]=(knapsack[x][j] + ((knapsack[x][j-1]*dp[y][1])%mod))%mod;
}
}
}
int sm=0;
for(int j=sz;j>=1;j--)
{
sm = ( sm + knapsack[x][j] ) % mod;
dp[x][1] = ( dp[x][1] + sm ) % mod;
}
sm=knapsack[x][0];
for(int j=1;j<=sz;j++)
{
dp[x][0] = ( dp[x][0] + sm ) % mod;
sm = ( sm + knapsack[x][j] ) % mod;
}
// Dp 1
for(int j=0;j<=sz;j++)knapsack[x][j]=0;
knapsack[x][0]=1;
for(auto y:ma[x])
{
for(int j=sz;j>=0;j--)
{
if(j==0)
{
knapsack[x][j]=(knapsack[x][j]*dp1[y][0])%mod;
}
else
{
knapsack[x][j]=(knapsack[x][j]*dp1[y][0])%mod;
knapsack[x][j]=(knapsack[x][j] + ((knapsack[x][j-1]*dp1[y][1])%mod))%mod;
}
}
}
sm=0;
for(int j=sz;j>=1;j--)
{
sm = ( sm + knapsack[x][j] ) % mod;
dp1[x][1] = ( dp1[x][1] + sm ) % mod;
}
sm=knapsack[x][0];
for(int j=1;j<=sz;j++)
{
dp1[x][0] = ( dp1[x][0] + sm ) % mod;
sm = ( sm + knapsack[x][j] ) % mod;
}
}
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];
compute();
}
int count_ways(int L, int R)
{
L-=n;
R-=n;
update(0,L,R);
return (int)dp[0][1];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |