#include "circuit.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1000002022;
const int INF = 1e9;
int n, m;
struct SegmentTree
{
struct Node
{
llong realVal, swapVal;
bool lazy;
Node()
{
realVal = swapVal = lazy = 0;
}
};
Node tree[2*MAXN]; // 2 * MAXN * 2
Node combine(Node left, Node right)
{
Node res;
res.realVal = left.realVal + right.realVal;
res.swapVal = left.swapVal + right.swapVal;
if (res.realVal >= MOD) res.realVal -= MOD;
if (res.swapVal >= MOD) res.swapVal -= MOD;
return res;
}
void push(int node, int l, int r)
{
if (!tree[node].lazy)
{
return;
}
std::swap(tree[node].realVal, tree[node].swapVal);
if (l < r)
{
tree[2*node].lazy ^= 1;
tree[2*node + 1].lazy ^= 1;
}
tree[node].lazy = 0;
}
void build(int l, int r, int node, llong vals[], llong b[])
{
if (l == r)
{
tree[node].realVal = vals[n + l];
tree[node].swapVal = 0;
if (b[n + l] == 0)
{
std::swap(tree[node].realVal, tree[node].swapVal);
}
return;
}
int mid = (l + r) / 2;
build(l, mid, 2*node, vals, b);
build(mid + 1, r, 2*node + 1, vals, b);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void update(int l, int r, int node, int queryL, int queryR)
{
push(node, l, r);
if (queryR < l || r < queryL)
{
return;
}
if (queryL <= l && r <= queryR)
{
tree[node].lazy ^= 1;
push(node, l, r);
return;
}
int mid = (l + r) / 2;
update(l, mid, 2*node, queryL, queryR);
update(mid + 1, r, 2*node + 1, queryL, queryR);
tree[node] = combine(tree[2*node], tree[2*node + 1]);
}
void build(llong multBy[], llong b[])
{
build(1, m, 1, multBy, b);
}
llong query(int l, int r)
{
update(1, m, 1, l - n + 1, r - n + 1);
return tree[1].realVal;
}
};
llong w[MAXN];
llong b[MAXN];
llong pw[MAXN];
llong multBy[MAXN];
std::vector <int> g[MAXN];
std::vector <int> prefixPW[MAXN];
std::vector <int> suffixPW[MAXN];
SegmentTree tree;
void initDFS(int node)
{
if (g[node].empty())
{
pw[node] = 1;
return;
}
pw[node] = g[node].size();
for (const int &i : g[node])
{
initDFS(i);
pw[node] *= pw[i];
pw[node] %= MOD;
}
prefixPW[node].resize(g[node].size());
prefixPW[node][0] = 1;
for (int i = 1 ; i < g[node].size() ; ++i)
{
prefixPW[node][i] = (prefixPW[node][i - 1] * pw[g[node][i - 1]]) % MOD;
}
suffixPW[node].resize(g[node].size());
suffixPW[node][g[node].size() - 1] = 1;
for (int i = (int)g[node].size() - 2 ; i >= 0 ; --i)
{
suffixPW[node][i] = (suffixPW[node][i + 1] * pw[g[node][i + 1]]) % MOD;
}
}
void findMult(int node, llong mult)
{
if (g[node].empty())
{
multBy[node] = mult;
return;
}
for (int i = 0 ; i < g[node].size() ; ++i)
{
findMult(g[node][i], (((mult * prefixPW[node][i]) % MOD) * suffixPW[node][i]) % MOD);
}
}
void init(int N, int M, std::vector <int> P, std::vector <int> A)
{
n = N;
m = M;
for (int i = 1 ; i < n + m ; ++i)
{
g[P[i] + 1].push_back(i + 1);
}
for (int i = n + 1 ; i <= n + m ; ++i)
{
if (A[i - n - 1] == 0)
{
w[i] = 1;
b[i] = 0;
} else
{
b[i] = 1;
w[i] = 0;
}
}
initDFS(1);
findMult(1, 1);
tree.build(multBy, b);
std::cout << tree.tree[1].realVal << '\n';
}
int count_ways(int L, int R)
{
return tree.query(L, R);
}
Compilation message
circuit.cpp: In function 'void initDFS(int)':
circuit.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 1 ; i < g[node].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
circuit.cpp: In function 'void findMult(int, llong)':
circuit.cpp:158:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | for (int i = 0 ; i < g[node].size() ; ++i)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23760 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23760 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23760 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
28880 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
28880 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23760 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23760 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23760 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
