| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 980224 | nextgenxing | 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.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F0R(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0Rd(i, n) for(int i = (n)-1; i >= 0; i--)
#define FORd(i, a, b) for(int i = (b)-1; i >= (a); i--)
#define ff first
#define ss second
const int MAX_N = 2e5+5;
const ll MOD = 1e9+2022;
ll add(ll a, ll b){ return (a+b)%MOD; }
ll sub(ll a, ll b){ return (a-b+MOD)%MOD; }
ll mul(ll a, ll b){ return (a*b)%MOD; }
ll ADD(ll &a, ll b){ return a=add(a, b); }
ll SUB(ll &a, ll b){ return a=sub(a, b); }
ll MUL(ll &a, ll b){ return a=mul(a, b); }
int N, M;
ll tot[MAX_N], w[MAX_N], state[MAX_N], sum[4*MAX_N], seg[4*MAX_N], lazy[4*MAX_N], active[4*MAX_N];
vector<int> adj[MAX_N];
void dfs(int curr){
if(adj[curr].size()) tot[curr] = adj[curr].size();
else tot[curr] = 1;
vector<ll> a(adj[curr].size()), b(adj[curr].size());
F0R(i, adj[curr].size()){
dfs(adj[curr][i]);
if(i) a[i] = mul(tot[adj[curr][i]], a[i-1]);
else a[i] = tot[adj[curr][i]];
b[i] = tot[adj[curr][i]];
MUL(tot[curr], tot[adj[curr][i]]);
}
F0Rd(i, adj[curr].size()-1) MUL(b[i], b[i+1]);
F0R(i, adj[curr].size()){
ll num = 1;
if(i) MUL(num, a[i-1]);
if(i < adj[curr].size()-1) MUL(num, b[i+1]);
MUL(w[adj[curr][i]], num);
}
}
void dfs2(int curr){
for(auto child : adj[curr]){
MUL(w[child], w[curr]);
dfs2(child);
}
}
void build(int idx, int l, int r){
if(l == r){
active[idx] = state[l];
sum[idx] = w[l+N];
seg[idx] = mul(active[idx], sum[idx]);
return;
}
int m = (l+r)/2;
build(2*idx, l, m), build(2*idx+1, m+1, r);
seg[idx] = add(seg[2*idx], seg[2*idx+1]);
sum[idx] = add(sum[2*idx], sum[2*idx+1]);
}
void prop(int idx, int l, int r){
if(lazy[idx]){
seg[idx] = sub(sum[idx], seg[idx]);
if(l != r){
lazy[2*idx] ^= lazy[idx];
lazy[2*idx+1] ^= lazy[idx];
} else active[idx] ^= 1;
lazy[idx] = 0;
}
}
void upd(int ql, int qr, int idx, int l, int r){
prop(idx, l, r);
if(ql > r || qr < l) return;
if(ql <= l && qr >= r){
lazy[idx] ^= 1;
prop(idx, l, r);
return;
}
int m = (l+r)/2;
upd(ql, qr, 2*idx, l, m), upd(ql, qr, 2*idx+1, m+1, r);
seg[idx] = add(seg[2*idx], seg[2*idx+1]);
}
ll qry(int ql, int qr, int idx, int l, int r){
prop(idx, l, r);
if(ql > r || qr < l) return 0;
if(ql <= l && qr >= r) return seg[idx];
int m = (l+r)/2;
return add(qry(ql, qr, 2*idx, l, m), qry(ql, qr, 2*idx+1, m+1, r));
}
void init(int n, int m, vector<int> P, vector<int> A){
N = n, M = m;
FOR(i, 1, n+m) adj[P[i]].push_back(i);
F0R(i, m) state[i] = A[i];
F0R(i, n+m) w[i] = 1;
dfs(0), dfs2(0);
build(1, 0, M-1);
}
int count_ways(int l, int r){
upd(l-N, r-N, 1, 0, M-1);
return qry(0, M-1, 1, 0, M-1);
}
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;
}