| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 710663 | myrcella | 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.
//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000002022
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
//#include "circuit.h"
const int maxn = 200010;
int a[maxn];
vector <int> edge[maxn];
int NN,MM;
pii tree[maxn*4];
int add[maxn*4];
int prod[maxn],cont[maxn];
void initt(int c,int cl,int cr) {
if (cl==cr) {
tree[c] = {a[cl]*cont[cl],(a[cl]^1)*cont[cl]};
return;
}
int mid=cl+cr>>1;
initt(c<<1,cl,mid);
initt(c<<1|1,mid+1,cr);
tree[c].fi = (tree[c<<1].fi + tree[c<<1|1].fi)%mod;
tree[c].se = (tree[c<<1].se + tree[c<<1|1].se)%mod;
// cout<<cl<<" "<<cr<<" "<<tree[c].fi<<" "<<tree[c].se<<endl;
}
void update(int c,int cl,int cr,int l,int r) {
if (l<=cl and cr<=r) {
add[c]^=1;
swap(tree[c].fi,tree[c].se);
return;
}
if (add[c]==1) {
add[c<<1]^=1,add[c<<1|1]^=1;
swap(tree[c<<1].fi,tree[c<<1].se);
swap(tree[c<<1|1].fi,tree[c<<1|1].se);
add[c] = 0;
}
int mid=cl+cr>>1;
if (l<=mid) update(c<<1,cl,mid,l,r);
if (r>mid) update(c<<1|1,mid+1,cr,l,r);
tree[c].fi = (tree[c<<1].fi + tree[c<<1|1].fi)%mod;
tree[c].se = (tree[c<<1].se + tree[c<<1|1].se)%mod;
return;
}
void dfs1(int u) {
prod[u] = SZ(edge[u]);
if (prod[u]==0) prod[u]=1;
for (int v:edge[u]) {
dfs1(v);
prod[u] = 1ll*prod[u]*prod[v]%mod;
}
return;
}
void dfs2(int u,int cur) {
if (SZ(edge[u])==0) {
cont[u]=cur;
return;
}
vector <int> pre,suf;
for (int v:edge[u]) {
pre.pb(prod[v]);
suf.pb(prod[v]);
}
rep(i,1,SZ(pre)) pre[i] = 1ll*pre[i-1]*pre[i]%mod;
for (int i = SZ(suf)-2;i>=0;i--) suf[i] = 1ll*suf[i+1]*suf[i]%mod;
rep(i,0,SZ(edge[u])) {
int tmp = 1;
if (i>0) tmp = 1ll*tmp*pre[i-1]%mod;
if (i+1<SZ(edge[u])) tmp = 1ll*tmp*suf[i+1]%mod;
dfs2(edge[u][i],1ll*cur*tmp%mod);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
NN=N,MM=M;
rep(i,1,SZ(P)) {
edge[P[i]].pb(i);
}
rep(i,0,SZ(A)) a[i+N]=A[i];
dfs1(0);
dfs2(0,1);
initt(1,N,N+M-1);
}
int count_ways(int L, int R) {
update(1,NN,NN+MM-1,L,R);
return tree[1].fi;
}
int main() {
int N, M, Q;
assert(3 == scanf("%d %d %d", &N, &M, &Q));
std::vector<int> P(N + M), A(M);
for (int i = 0; i < N + M; ++i) {
assert(1 == scanf("%d", &P[i]));
}
for (int j = 0; j < M; ++j) {
assert(1 == scanf("%d", &A[j]));
}
init(N, M, P, A);
for (int i = 0; i < Q; ++i) {
int L, R;
assert(2 == scanf("%d %d", &L, &R));
printf("%d\n", count_ways(L, R));
}
return 0;
}