#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[lc[v]][0],dp1[lc[v]][0]);
swap(dp[rc[v]][1],dp1[rc[v]][1]);
lazy[v]=0;
}
void update(int v,int l,int r,int ql,int qr)
{
if(qr<l or r<ql) // nothing changes here
return;
if(ql<=l and r<=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);
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);
return (int)dp[0][1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
4th lines differ - on the 1st token, expected: '1', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
4th lines differ - on the 1st token, expected: '1', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
4th lines differ - on the 1st token, expected: '1', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
708 ms |
10704 KB |
Output is correct |
| 2 |
Correct |
1010 ms |
16208 KB |
Output is correct |
| 3 |
Correct |
941 ms |
16208 KB |
Output is correct |
| 4 |
Correct |
1038 ms |
16288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
708 ms |
10704 KB |
Output is correct |
| 2 |
Correct |
1010 ms |
16208 KB |
Output is correct |
| 3 |
Correct |
941 ms |
16208 KB |
Output is correct |
| 4 |
Correct |
1038 ms |
16288 KB |
Output is correct |
| 5 |
Incorrect |
1615 ms |
11208 KB |
3rd lines differ - on the 1st token, expected: '249436868', found: '806835274' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
4th lines differ - on the 1st token, expected: '1', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
4th lines differ - on the 1st token, expected: '1', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4952 KB |
4th lines differ - on the 1st token, expected: '1', found: '4' |
| 2 |
Halted |
0 ms |
0 KB |
- |
