#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
struct segment_tree{
int n, m;
long long tree_size[200002], sum[400004], counting[400004], multiplier[100001];
bool toggle[400004];
vector<int> child[100001], A;
vector<long long> left_product[100001], right_product[100001];
void init(int N, int M, vector<int> p, vector<int> a){
n = N;
m = M;
A = a;
tree_size[0] = 1LL;
for(int i = 1; i < N+M; i++){
tree_size[i] = 1LL;
child[p[i]].push_back(i);
left_product[p[i]].push_back(0LL);
right_product[p[i]].push_back(0LL);
}
}
void calculate_size(int N){
if(N >= n)return;
tree_size[N] = (long long) child[N].size();
for(int i = 0; i < child[N].size(); i++){
calculate_size(child[N][i]);
left_product[N][i] = tree_size[child[N][i]];
right_product[N][i] = tree_size[child[N][i]];
tree_size[N] *= tree_size[child[N][i]];
tree_size[n] %= 1000002022;
}
for(int i = 1; i < child[N].size(); i++){
left_product[N][i] *= left_product[N][i-1];
left_product[N][i] %= 1000002022;
}
for(int i = child[N].size()-1; i; i--){
right_product[N][i-1] *= right_product[N][i];
right_product[N][i-1] %= 1000002022;
}
}
void calculate_multiplier(int N, long long M){
if(N >= n){
multiplier[N] = M;
return;
}
if(child[N].size() == 1){
calculate_multiplier(child[N][0], M);
return;
}
for(int i = 0; i < child[N].size(); i++){
if(!i)calculate_multiplier(child[N][i], (M*right_product[N][1])%1000002022);
else if(i+1==child[N].size())calculate_multiplier(child[N][i], (M*left_product[N][child[N].size()-2])%1000002022);
else calculate_multiplier(child[N][i], (M*((right_product[N][i+1]*left_product[N][i-1])%1000002022))%1000002022);
}
}
void create_tree(int N, int l, int r){
toggle[N] = false;
if(l == r){
sum[N] = multiplier[n+r-1];
if(A[r-1])counting[N] = multiplier[n+r-1];
else counting[N] = 0LL;
return;
}
create_tree(2*N, l, (l+r)/2);
create_tree(2*N+1,(l+r)/2+1, r);
sum[N] = (sum[2*N] + sum[2*N+1]) % 1000002022;
counting[N] = (counting[2*N] + counting[2*N+1]) % 1000002022;
}
void lazy_update(int N){
if(toggle[N]){
toggle[2*N] = !toggle[2*N];
toggle[2*N+1] = !toggle[2*N+1];
counting[2*N] = (sum[2*N]-counting[2*N]+1000002022) % 1000002022;
counting[2*N+1] = (sum[2*N+1]-counting[2*N+1]+1000002022) % 1000002022;
}
}
void update(int N, int l, int r, int s, int t){
if(l > t || r < s)return;
if(l <= s && r >= t){
toggle[N] = !toggle[N];
counting[N] = (sum[N]-counting[N]+1000002022) % 1000002022;
return;
}
lazy_update(N);
update(2*N, l, r, s, (s+t)/2);
update(2*N+1, l, r, (s+t)/2+1, t);
counting[N] = (counting[2*N] + counting[2*N+1]) % 1000002022;
}
} A;
void init(int N, int M, vector<int> p, vector<int> a) {
A.init(N, M, p, a);
A.calculate_size(0);
A.calculate_multiplier(0, 1LL);
A.create_tree(1, 1, M);
}
int count_ways(int L, int R) {
A.update(1, L-A.n+1, R-A.n+1, 1, A.m);
return A.counting[1];
}
Compilation message
circuit.cpp: In member function 'void segment_tree::calculate_size(int)':
circuit.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i = 0; i < child[N].size(); i++){
| ~~^~~~~~~~~~~~~~~~~
circuit.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i = 1; i < child[N].size(); i++){
| ~~^~~~~~~~~~~~~~~~~
circuit.cpp: In member function 'void segment_tree::calculate_multiplier(int, long long int)':
circuit.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int i = 0; i < child[N].size(); i++){
| ~~^~~~~~~~~~~~~~~~~
circuit.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | else if(i+1==child[N].size())calculate_multiplier(child[N][i], (M*left_product[N][child[N].size()-2])%1000002022);
| ~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14168 KB |
5th lines differ - on the 1st token, expected: '481', found: '511' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14168 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14168 KB |
5th lines differ - on the 1st token, expected: '481', found: '511' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
18380 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
417 ms |
18380 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
14168 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '0' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14168 KB |
5th lines differ - on the 1st token, expected: '481', found: '511' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14168 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
14168 KB |
5th lines differ - on the 1st token, expected: '481', found: '511' |
| 4 |
Halted |
0 ms |
0 KB |
- |
