#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1'000'002'022;
int n, m;
vector<ll> storage;//When you call the constructor, make sure that everything is reduced modulo MOD
vector<int> a;
class Lazy{
public:
int L, R;
ll total_sum;
ll active;//MAKE SURE THAT THIS IS ALWAYS ACCURATE
bool flip;//When I need to flip, I don't need to flip myself, I need to flip my children only
Lazy* left;
Lazy* right;
Lazy(int l, int r)
{
L = l; R = r;
flip = 0;
if (L==R)
{
left = nullptr;
right = nullptr;
total_sum = storage[L];
if (a[L] == 1)
active = total_sum;
else
active = 0;
}
else
{
int mid = (l+r)/2;
left = new Lazy(l, mid);
right = new Lazy(mid+1, r);
total_sum = left->total_sum + right->total_sum;
active = left->active + right->active;
}
}
void update()
{
//assumption: My children could have just updated themselves, and so should I
if (left!=nullptr)
active = left->active + right->active;
}
void pancake_flip()
{
//assumption: this is updated, and I want to update myself
active = total_sum - active;
if (flip == 0)
flip = 1;
else
flip = 0;
}
void push_down()
{
//assumption: this is updated, and I want to update my children
if (flip == 1)
{
flip = 0;
if (left != nullptr)
{
left->pancake_flip();
right->pancake_flip();
}
}
}
void range_flip(int range_l, int range_r)
{
int intersect_l = max(range_l, L);
int intersect_r = min(range_r, R);
if ((intersect_l == L) and (intersect_r==R))
{
pancake_flip();
push_down();
}
else if (intersect_l <= intersect_r)
{
push_down();
left->range_flip(range_l, range_r);
right->range_flip(range_l, range_r);
update();
}
}
};
Lazy circ = Lazy(0, 0);
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
vector<ll> degrees(N, 0);
for (int i=1; i<(N+M); i++)
degrees[P[i]]++;
vector<vector<bool>> ancestor(N+M, vector<bool> (N, 0));
for (int i=1; i<(N+M); i++)
{
int par = P[i];
for (int j=0; j<N; j++)
ancestor[i][j] = ancestor[par][j];
ancestor[i][par] = 1;
}
a = A;
for (int i=N; i<(N+M); i++)
{
ll ans = 1;
for (int j = 0; j<N; j++)
if (ancestor[i][j] == 0)
ans = (ans*degrees[j])%MOD;
storage.push_back(ans);
}
circ = Lazy(0, M-1);
}
int count_ways(int L, int R) {
L -= n;
R -= n;
circ.range_flip(L, R);
/*for (int i=L; i<=R; i++)
a[i] = 1-a[i];
ll total = 0;
for (int i=0; i<m; i++)
{
if (a[i]==1)
total = total+storage[i];
}*/
ll fa = circ.active%MOD;
int ffa = fa;
return ffa;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
