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;
typedef long long ll;
const int mod=1e9+2022;
const int N=2e5;
int n, m, q;
vector<int> adj[N];
int p[N];
int a[N];
int sum[4*N], con[4*N], c[N];
ll prod[N];
int add(int a, int b){
return ((a+mod)%mod+(b+mod)%mod)%mod;
}
void add2(int &a, int b){
a=add(a,b);
}
int mult(ll a, ll b){
return (a*b)%mod;
}
void mult2(ll &a, ll b){
a=mult(a,b);
}
void dfs(int x){
prod[x]=x<n?adj[x].size():1;
for(int k:adj[x]){
dfs(k);
mult2(prod[x], prod[k]);
}
}
void dfs2(int x){
int p=adj[x].size();
vector<ll> pre(p), suf(p);
for(int i=0; i<p; i++){
int k=adj[x][i];
pre[i]=suf[i]=prod[k];
}
for(int i=1; i<p; i++){
mult2(pre[i], pre[i-1]);
}
for(int i=p-2; i>=0; i--){
mult2(suf[i], suf[i+1]);
}
for(int i=0; i<p; i++){
int k=adj[x][i];
c[k]=mult(c[x], mult(i?pre[i-1]:1, i<p-1?suf[i+1]:1));
dfs2(k);
}
}
short lazy[4*N];
void build(int x, int lx, int rx){
if(rx-lx==1){
con[x]=a[lx]?c[lx+n]:0;
// cout << "c[" << lx+n << "] " << c[lx+n] << "\n";
sum[x]=c[lx+n];
return;
}
int m=(lx+rx)/2;
build(2*x+1, lx, m);
build(2*x+2, m, rx);
con[x]=add(con[2*x+1], con[2*x+2]);
sum[x]=add(sum[2*x+1], sum[2*x+2]);
}
void push(int x, int lx, int rx){
if(rx-lx==1 || !lazy[x]) return;
for(int y=2*x+1; y<=2*x+2; y++){
con[y]=sum[y]-con[y];
lazy[y]^=1;
}
lazy[x]=0;
}
void tog(int l, int r, int x=0, int lx=0, int rx=m){
push(x, lx, rx);
if(lx>=r || rx<=l) return;
if(lx>=l && rx<=r){
con[x]=sum[x]-con[x];
lazy[x]=1;
return;
}
int m=(lx+rx)/2;
tog(l, r, 2*x+1, lx, m);
tog(l, r, 2*x+2, m, rx);
con[x]=add(con[2*x+1], con[2*x+2]);
}
void init(int n, int m, std::vector<int> P, std::vector<int> A) {
for(int i=0; i<n+m; i++){
p[i]=P[i];
if(i) adj[p[i]].push_back(i);
}
for(int i=0; i<m; i++) a[i]=A[i];
dfs(0);
c[0]=1;
dfs2(0);
build(0, 0, m);
}
int count_ways(int l, int r) {
l-=n; r-=n;
tog(l, r+1);
return con[0];
}
# | 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... |