#include <bits/stdc++.h>
using namespace std;
#include "circuit.h"
#define F first
#define S second
typedef int ll;
int const Mx = 1e6 + 10 , mod = 1000002022;
int n , m , N , M , state[Mx] , ways[Mx][3] , segmentTree = 1 , mn[Mx] , Left[Mx] , Right[Mx] , op[Mx];
vector<ll>adj[Mx];
inline long long Mul(long long x , long long y) {
x %= mod;
y %= mod;
return (x * y) % mod;
}
inline long long Add(long long x , long long y) {
x %= mod;
y %= mod;
return (x + y) % mod;
}
inline bool cmp(int a , int b) {
return mn[a] < mn[b];
}
inline void Order(int node) {
mn[node] = 1e9;
for(auto next : adj[node]) {
Order(next);
mn[node] = min(mn[node] , mn[next]);
}
sort(adj[node].begin() , adj[node].end() , cmp);
if(node >= N) mn[node] = node;
}
inline void calc(int node) {
ways[node][1] = ways[node][0] = 0;
vector<ll>Dp;
Dp.assign(adj[node].size() + 2 , 0);
Dp[0] = 1;
for(int i = 0 ; i < adj[node].size() ; ++i) {
int next = adj[node][i];
for(int cnt = i + 1 ; cnt >= 0 ; --cnt) {
//cout << "cnt = " << cnt << endl;
Dp[cnt] = Add(Mul(Dp[cnt] , ways[next][0]) , cnt > 0 ? (Mul(Dp[cnt - 1] , ways[next][1])) : 0 );
}
}
for(int cnt = 0 ; cnt <= adj[node].size() ; ++cnt) {
ways[node][1] = Add(ways[node][1] , Mul(Dp[cnt] , cnt));
ways[node][0] = Add(ways[node][0] , Mul(Dp[cnt] , (adj[node].size() - cnt)));
}
}
inline void Build(int node = 0) {
if(node >= N) {
if(state[node] == 1) ways[node][1] = 1;
else ways[node][1] = 0;
ways[node][0] = 1 - ways[node][1];
return;
}
Build(Left[node]);
Build(Right[node]);
calc(node);
}
void init(int X , int Y , vector<int> P, vector<int> A) {
N = X , M = Y;
if(M & (M - 1) != 0) segmentTree = 0;
if(M != N + 1) segmentTree = 0;
for(int i = 1 ; i < P.size() ; ++i) {
adj[P[i]].push_back(i);
if(P[i] != (i - 1) / 2) segmentTree = 0;
}
for(int i = 0 ; i < A.size() ; ++i) state[i + N] = A[i];
if(segmentTree) {
Order(0);
for(int node = 0 ; node < N ; ++node) {
Left[node] = adj[node][0];
Right[node] = adj[node][1];
}
Build();
}
}
inline void Dfs(int node) { //cout << "node = " << node << endl;
for(auto next : adj[node]) Dfs(next);
if(node >= N) {
if(state[node] == 1) ways[node][1] = 1;
else ways[node][1] = 0;
ways[node][0] = 1 - ways[node][1];
return;
}
calc(node);
return;
}
inline void Push(int node) {
if(op[node] == 0) return;
op[Left[node]] ^= 1;
op[Right[node]] ^= 1;
op[node] = 0;
swap(ways[Left[node]][1] , ways[Left[node]][0]);
swap(ways[Right[node]][1] , ways[Right[node]][0]);
return;
}
inline void Update(int l , int r , int node = 0 , int lx = 1 , int rx = M) {
if(lx > r && rx < l) return;
if(lx >= l && rx <= r) {
op[node] ^= 1;
swap(ways[node][1] , ways[node][0]);
return;
}
Push(node);
int mid = (lx + rx) / 2;
Update(l , r , Left[node] , lx , mid);
Update(l , r , Right[node] , mid + 1 , rx);
calc(node);
}
int count_ways(int L, int R) {
if(segmentTree) {
Update(L - N + 1 , R - N + 1);
return ways[0][1];
}
for(int i = L ; i <= R ; ++i) state[i] = !state[i];
Dfs(0);
return ways[0][1];
}
Compilation message
circuit.cpp: In function 'void calc(int)':
circuit.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i = 0 ; i < adj[node].size() ; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:52:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for(int cnt = 0 ; cnt <= adj[node].size() ; ++cnt) {
| ~~~~^~~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:74:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
74 | if(M & (M - 1) != 0) segmentTree = 0;
| ~~~~~~~~^~~~
circuit.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 1 ; i < P.size() ; ++i) {
| ~~^~~~~~~~~~
circuit.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0 ; i < A.size() ; ++i) state[i + N] = A[i];
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1412 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
778 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1412 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
760 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
760 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
778 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1412 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1412 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
