| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 914470 | ALTAKEXE | Digital Circuit (IOI22_circuit) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll MOD = 1000002022;
ll n, m;
ll p[1000001], sz[1000001], v[100001], d1[200001], d2[200001];
bool lz[2000001];
vector<ll> d[100001];
void dfs(ll u)
{
for (auto v : d[u])
{
sz[v] = sz[u] + 1;
dfs(v);
}
}
void build(ll l, ll r, ll i, vector<ll> &t)
{
if (l == r)
{
if (t[l])
{
d1[i] = v[l];
}
else
{
d2[i] = v[l];
}
return;
}
ll md = (l + r) / 2;
build(l, md, 2 * i, t);
build(md + 1, r, 2 * i + 1, t);
d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void lazy(ll l, ll r, ll i)
{
if (!lz[i])
return;
lz[i] = 0;
swap(d1[i], d2[i]);
if (l == r)
return;
lz[2 * i] = !lz[2 * i];
lz[2 * i + 1] = !lz[2 * i + 1];
}
void update(ll l, ll r, ll i, ll ql, ll qr)
{
lazy(l, r, i);
if (r < ql || qr < l)
return;
if (ql <= l && r <= qr)
{
lz[i] = 1;
lazy(l, r, i);
return;
}
ll md = (l + r) / 2;
update(l, md, 2 * i, ql, qr);
update(md + 1, r, 2 * i + 1, ql, qr);
d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void init(ll N, ll M, vector<ll> P, vector<ll> A)
{
p[0] = 1;
n = N;
m = M;
for (ll i = 1; i < N + M; i++)
p[i] = (p[i - 1] * 2) % MOD;
for (ll i = 1; i < N + M; i++)
d[P[i]].push_back(i);
dfs(0);
for (ll i = N; i < N + M; i++)
v[i - N] = p[N - sz[i]];
build(0, M - 1, 1, A);
}
ll count_ways(ll L, ll R)
{
update(0, m - 1, 1, L - n, R - n);
return d1[1];
}