#include <bits/stdc++.h>
#include "circuit.h"
#define MAX 200001
using namespace std;
typedef long long ll;
int n,m;
const int mod=1000002022;
vector<vector<int>> g;
long long dp[MAX],dp1[MAX];
void dfs(int v){
if(v>=n){
dp[v]=1;
return;
}
dp[v]=(int)g[v].size();
for(auto x:g[v]){
dfs(x);
dp[v]*=dp[x];
dp[v]%=mod;
}
}
void dfs1(int v){
if(v>=n){
return;
}
int sz=(int)g[v].size();
vector<int> pref(sz),suf(sz);
for(int i=0;i<sz;i++){
pref[i]=dp[g[v][i]];
if(i){
pref[i]*=pref[i-1];
pref[i]%=mod;
}
}
for(int i=sz-1;i>=0;i--){
suf[i]=dp[g[v][i]];
if(i!=sz-1){
suf[i]*=suf[i+1];
suf[i]%=mod;
}
}
for(int i=0;i<sz;i++){
int pr,sf;
pr=sf=1;
if(i){
pr=pref[i-1];
}
if(i!=sz-1){
sf=suf[i+1];
}
dp1[g[v][i]]=dp1[v];
dp1[g[v][i]]*=pr;
dp1[g[v][i]]%=mod;
dp1[g[v][i]]*=sf;
dp1[g[v][i]]%=mod;
dfs1(g[v][i]);
}
}
ll sm(ll x,ll y){
ll res=(x+y)%mod;
if(res<0){
res+=mod;
}
return res;
}
ll ml(ll x,ll y){
ll res=(x*y)%mod;
if(res<0){
res+=mod;
}
return res;
}
struct segtree{
vector<ll> sums;
vector<ll> lazy;
int size;
void init(int n){
size=1;
while(size<n){
size*=2;
}
sums.assign(2*size,0LL);
lazy.assign(2*size,1LL);
}
void build(int x,int lx,int rx,vector<int> &a){
if(rx-lx==1){
if(lx<(int)a.size()){
sums[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(2*x+1,lx,m,a);
build(2*x+2,m,rx,a);
sums[x]=sm(sums[2*x+1],sums[2*x+2]);
}
void build(vector<int> &a){
build(0,0,size,a);
}
void propogate(int x,int lx,int rx){
if(rx-lx==1){
return;
}
sums[2*x+1]=ml(sums[2*x+1],lazy[x]);
sums[2*x+2]=ml(sums[2*x+2],lazy[x]);
lazy[2*x+1]=ml(lazy[2*x+1],lazy[x]);
lazy[2*x+2]=ml(lazy[2*x+2],lazy[x]);
lazy[x]=1;
}
void upd(int x,int lx,int rx,int l,int r,int v){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return;
}
if(lx>=l && rx<=r){
sums[x]=ml(sums[x],v);
lazy[x]=ml(lazy[x],v);
return;
}
int m=(lx+rx)/2;
upd(2*x+1,lx,m,l,r,v);
upd(2*x+2,m,rx,l,r,v);
sums[x]=sm(sums[2*x+1],sums[2*x+2]);
}
void upd(int l,int r,int v){
return upd(0,0,size,l,r,v);
}
ll get(int x,int lx,int rx,int l,int r){
propogate(x,lx,rx);
if(rx<=l || lx>=r){
return 0;
}
if(lx>=l && rx<=r){
return sums[x];
}
int m=(lx+rx)/2;
ll s1,s2;
s1=get(2*x+1,lx,m,l,r);
s2=get(2*x+2,m,rx,l,r);
return sm(s1,s2);
}
ll get(int l,int r){
return get(0,0,size,l,r);
}
};
segtree st;
ll res=0;
void init(int N, int M, vector<int> P, vector<int> A) {
n=N;
m=M;
g.resize(n+m);
for(int i=1;i<n+m;i++){
g[P[i]].push_back(i);
}
dfs(0);
dp1[0]=1;
dfs1(0);
st.init(m);
vector<int> b;
for(int i=0;i<m;i++){
if(A[i]){
res=sm(res,dp1[n+i]);
b.push_back(-dp1[n+i]);
}
else{
b.push_back(dp1[n+i]);
}
}
st.build(b);
}
int count_ways(int L, int R) {
st.upd(L-n,R-n+1,-1);
res+=st.get(L-n,R-n+1);
res%=mod;
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
1st lines differ - on the 1st token, expected: '1', found: '1000002021' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
1st lines differ - on the 1st token, expected: '1', found: '1000002021' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
1st lines differ - on the 1st token, expected: '1', found: '1000002021' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
406 ms |
7256 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '357186114' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
406 ms |
7256 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '357186114' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
1st lines differ - on the 1st token, expected: '1', found: '1000002021' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
1st lines differ - on the 1st token, expected: '1', found: '1000002021' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
1st lines differ - on the 1st token, expected: '1', found: '1000002021' |
| 2 |
Halted |
0 ms |
0 KB |
- |
