#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD=1000002022;
vector<int> allprod; //for each node, product of all threshold totals in subtree of the node
vector<int> subt_values; //for each node, product of all threshold totals not on path from node to root
vector<vector<int>> children;
vector<int> ison;
int dfs2currentprod = 1; //the current product of the dfs2 values
int curS = 0;
int n,m;
void dfs1(int node) {
allprod[node] = 1;
for (int j:children[node]) {
dfs1(j);
allprod[node] *= allprod[j];
allprod[node]%=MOD;
}
if (children[node].size()) allprod[node]*=children[node].size();
allprod[node]%=MOD;
}
void dfs2(int node) {
//calculate the product of all threshold totals not on the path from node to root, for each leaf
if (!children[node].size()) {
subt_values[node] = dfs2currentprod;
return;
}
int oldprod = dfs2currentprod;
int k=children[node].size();
vector<int> prefprod(k+1,1); //product of sub product for all children with index<i
for (int i=1; i<=k; i++) {
prefprod[i] = prefprod[i-1]*allprod[children[node][i-1]];
prefprod[i]%=MOD;
}
vector<int> suffprod(k+1,1); //product of sub product for all children with index>=i
for (int i=k-1; i>=0; i--) {
suffprod[i] = suffprod[i+1]*allprod[children[node][i]];
suffprod[i]%=MOD;
}
/*cout << "DFS " << node << " " << dfs2currentprod;
for (int i=0; i<k+1; i++) {
cout << i <<" " << prefprod[i] <<" " << suffprod[i] << endl;
}*/
for (int i=0; i<k; i++) {
int totprod=prefprod[i]*suffprod[i+1];
totprod%=MOD;
totprod*=oldprod;
totprod%=MOD;
dfs2currentprod = totprod;
dfs2(children[node][i]);
}
}
vector<int> prefsums; //prefsums[j] = sum of normal contribution BEFORE j
//so do like prefsums[r+1]-prefsums[l]
int maxn=262144;
int MAXN=maxn;
vector<int> tree;
vector<int> lazy;
int getcont(int tl, int tr) {
return prefsums[tr+1]-prefsums[tl];
}
void push(int node, int tl, int tr) {
if (lazy[node]==0) {
return;
}
if (lazy[node]==1) {
tree[node] = ((getcont(tl,tr)-tree[node])%MOD+MOD)%MOD;
}
if (tl<tr) {
lazy[node*2] ^= lazy[node];
lazy[node*2+1]^=lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int tl, int tr) {
//cout << "updating " << node <<" " << l <<" "<<r <<" "<< tl <<" " << tr << endl;
//flip all bits between l and r inclusive
if (l>r) {
return;
}
if (l>tr || r<tl) {
return;
}
push(node,tl,tr);
if (l<=tl && tr<=r) {
//full overlap
tree[node] = getcont(tl, tr) - tree[node];
if (tl<tr) {
lazy[node*2] ^= 1;
lazy[node*2+1] ^= 1;
}
return;
}
int m=(tl+tr)/2;
update(node*2, l, r, tl, m);
update(node*2+1, l, r, m+1, tr);
tree[node] = tree[node*2]+tree[node*2+1];
tree[node]+=MOD;
tree[node]%=MOD;
return;
}
int query(int node, int l, int r, int tl, int tr) {
//cout << "querying " << node <<" " << l <<" "<<r <<" "<< tl <<" " << tr << endl;
if (l>r) {
return 0;
}
if (l>tr || r<tl) {
return 0;
}
push(node,tl,tr);
if (l<=tl && tr<=r) {
return tree[node];
}
int m=(tl+tr)/2;
int q1 = query(node*2, l, r, tl, m);
int q2 = query(node*2+1, l, r, m+1, tr);
int qsum = q1+q2;
return qsum;
}
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
n=N;
m=M;
allprod = vector<int>(N+M, 1);
subt_values = vector<int>(N+M, 1);
ison = vector<int>(M, 1);
children=vector<vector<int>>(N+M);
tree=vector<int>(4*maxn,0);
lazy=vector<int>(4*maxn,0); //bit
for (int i=1; i<N+M; i++) {
children[P[i]].push_back(i);
}
dfs1(0);
dfs2(0);
/*for (int i=0; i<N+M; i++) {
cout << i <<" " << allprod[i] << endl;
}
for (int i=0; i<N+M; i++) {
cout << i <<" " << subt_values[i] << endl;
}*/
for (int i=N; i<N+M; i++) {
ison[i-N] = A[i-N];
if (A[i-N]==1) {
update(1, i-N, i-N, 0, maxn-1);
}
}
prefsums=vector<int>(MAXN+1, 0);
prefsums[0] = 0;
for (int i=1; i<MAXN+1; i++) {
//cout << i << endl;
int sv;
if (i>M) {
sv=0;
}
else {
sv=subt_values[i-1+N];
}
prefsums[i] = (prefsums[i-1]+sv)%MOD;
}
}
/*3 6 5
-1 0 0 1 1 1 2 2 0
0 0 0 0 0 0
3 8*/
int32_t count_ways(int32_t L, int32_t R) {
/**for (int i=L; i<=R; i++) {
ison[i-n] = 1-ison[i-n];
}
int su=0;
for (int i=0; i<m; i++) {
//cout << i <<" " << subt_values[i+n] << endl;
su+=ison[i]*subt_values[i+n];
su%=MOD;
}*/
update(1,L-n, R-n, 0, maxn-1);
int su=query(1, 0, maxn-1, 0, maxn-1);
return su;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18776 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
18776 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18776 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
43232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
43232 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
18776 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18776 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
18776 KB |
4th lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
