#include "circuit.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef long long ll;
int NN, MM;
const ll N = 2e5 + 10, mod = 1000002022;
int p[N], d[N];
int lazy[4 * N];
int a[N], cnt[N];
ll pref[N];
ll c[N];
ll tree2[4 * N];
void build_tree2(int v, int tl, int tr) {
if (tl == tr) {
if (a[tl]) {
tree2[v] = pref[tl];
if (tl) tree2[v] -= pref[tl - 1];
tree2[v] = (tree2[v] + mod) % mod;
}
else tree2[v] = 0;
}
else {
int tm = (tl + tr) / 2;
build_tree2(2 * v, tl, tm);
build_tree2(2 * v + 1, tm + 1, tr);
tree2[v] = tree2[2 * v] + tree2[2 * v + 1];
tree2[v] %= mod;
}
}
void pushh2(int v, int tl, int tr) {
if (lazy[v]) {
lazy[v] = 0;
if (tl != tr) {
lazy[2 * v] = (lazy[2 * v] + 1) % 2;
lazy[2 * v + 1] = (lazy[2 * v + 1] + 1) % 2;
int tm = (tl + tr) / 2;
ll u = pref[tm];
if (tl) u -= pref[tl - 1];
u += mod;
u %= mod;
tree2[2 * v] = (u + mod - tree2[2 * v]) % mod;
u = pref[tr] - pref[tm] + mod;
u %= mod;
tree2[2 * v + 1] = (u + mod - tree2[2 * v + 1]) % mod;
}
}
}
void update2(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
lazy[v] = (lazy[v] + 1) % 2;
ll u = pref[tr];
if (tl) u -= pref[tl - 1];
u += mod;
u %= mod;
tree2[v] = (u - tree2[v] + mod) % mod;
return;
}
pushh2(v, tl, tr);
int tm = (tl + tr) / 2;
update2(2 * v, tl, tm, l, r);
update2(2 * v + 1, tm + 1, tr, l, r);
tree2[v] = tree2[2 * v] + tree2[2 * v + 1];
tree2[v] %= mod;
}
ll dp[N];
vector <vector<int>> G;
void dfs(int v, int p) {
ll u = 1;
bool ch = false;
for (auto it : G[v]) {
if (it == p) continue;
dfs(it, v);
u *= dp[it];
u %= mod;
ch = true;
}
if (!ch) {
dp[v] = 1;
return;
}
u *= (ll)G[v].size();
u %= mod;
dp[v] = u;
}
void dfss(int v, int p) {
vector <int> children;
for (auto it : G[v]) {
if (it == p) continue;
children.push_back(it);
}
vector <ll> pref((int)children.size()), suff((int)children.size());
for (int i = 0; i < (int)children.size(); i++) {
pref[i] = dp[children[i]];
if (i) pref[i] = (pref[i - 1] * pref[i]) % mod;
}
for (int i = (int)children.size() - 1; i >= 0; i--) {
suff[i] = dp[children[i]];
if (i != (int)children.size() - 1) {
suff[i] = (suff[i] * suff[i + 1]) % mod;
}
}
for (int i = 0; i < (int)children.size(); i++) {
ll u = 1;
if (i) u *= pref[i - 1];
u %= mod;
if (i != (int)children.size() - 1) u *= suff[i + 1];
u %= mod;
c[children[i]] = u;
}
for (auto it : G[v]) {
if (it == p) continue;
dfss(it, v);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
NN = N, MM = M;
G.resize(N + M);
for (int i = 0; i < N + M; i++) {
if (i) {
G[P[i]].push_back(i);
}
}
dfs(0, -1);
dfss(0, -1);
for (int i = 0; i < M; i++) {
pref[i] = c[i + N];
if (i) pref[i] += pref[i - 1];
pref[i] %= mod;
}
build_tree2(1, 0, MM - 1);
}
int count_ways(int L, int R) {
update2(1, 0, MM - 1, L - NN, R - NN);
return tree2[1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '509', found: '69' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
380 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '2' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '509', found: '69' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
5556 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
471 ms |
5556 KB |
1st lines differ - on the 1st token, expected: '431985922', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
380 KB |
1st lines differ - on the 1st token, expected: '52130940', found: '2' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '509', found: '69' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '509', found: '69' |
| 4 |
Halted |
0 ms |
0 KB |
- |
