| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 925519 | beaboss | 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.
// Source: https://oj.uz/problem/view/IOI22_circuit
//
#include "bits/stdc++.h"
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
bool ckmin(ll& a, ll b){ return b < a ? a = b, true : false; }
bool ckmax(ll& a, ll b){ return b > a ? a = b, true : false; }
#define lc (i << 1)
#define rc (i << 1) + 1
const ll N = 2e5 + 10;
const ll MOD = 1e9 + 2022;
ll n, m;
ll p[N], contrib[N], sub[N];
vi adj[N];
void calc_sub(ll cur) {
sub[cur] = 1;
for (auto val: adj[cur]) {
calc_sub(val);
sub[cur] = sub[cur] * sub[val] % MOD;
}
if (adj[cur].size()) sub[cur] = sub[cur] * adj[cur].size() % MOD;
// cout << ' ' << cur << sub[cur] << adj[cur].size() << endl;
}
void dfs(ll cur, ll prod = 1) {
// cout << cur << prod << endl;
contrib[cur]=prod;
vi pref(adj[cur].size()), suff(adj[cur].size());
FOR(i, 0, adj[cur].size()) {
if (i) pref[i] = pref[i-1];
else pref[i]=1;
pref[i] = pref[i] * sub[adj[cur][i]] % MOD;
}
for (ll i = adj[cur].size() - 1; i >= 0; i--) {
if (i != adj[cur].size() - 1) suff[i] = suff[i + 1];
else suff[i]=1;
suff[i] = suff[i] * sub[adj[cur][i]] % MOD;
}
FOR(i, 0, adj[cur].size()) {
ll here = prod;
if (i) here = here * pref[i-1] % MOD;
if (i != adj[cur].size() - 1) here = here * suff[i+1] % MOD;
dfs(adj[cur][i], here);
}
}
struct node {
ll val;
ll sum;
ll flip;
} st[4 * N];
void up(ll i) {
st[i].val = (st[rc].val + st[lc].val) % MOD;
st[i].sum = (st[rc].sum + st[lc].sum) % MOD;
}
void down(ll i) {
if (!st[i].flip) return;
st[rc].val = (st[rc].sum - st[rc].val + MOD) % MOD;
st[lc].val = (st[lc].sum - st[lc].val + MOD) % MOD;
st[rc].flip = !st[rc].flip;
st[lc].flip = !st[lc].flip;
st[i].flip = 0;
}
void adjust(ll ind, ll val, ll on, ll i = 1, ll l = 0, ll r = N) { // should happen before range updates
if (r <= l) return;
if (r - l == 1 && l == ind) {
// cout << val << endl;
// assert(on <= 1);
st[i].flip = 0;
st[i].sum = val;
st[i].val = st[i].sum * on;
// cout << l << r << ' ' << st[i].val << endl;
return;
}
// if (r - l == 1) return;
// cout << l << r << endl;
// cout << val << endl;
ll m = (l + r) / 2;
if (m > ind) adjust(ind, val, on, lc, l, m);
else adjust(ind, val, on, rc, m, r);
up(i);
// cout << l << r << ' ' << st[i].val << ' ' << st[rc].val << ' ' << st[lc].val << endl;
}
void update(ll ul, ll ur, ll i = 1, ll l = 0, ll r = N) {
if (r <= l) return;
if (ul <= l && r <= ur) { // fully contained
st[i].val = (st[i].sum - st[i].val + MOD) % MOD;
st[i].flip = !st[i].flip;
// cout << l << ' ' << r << ' ' << st[i].val << endl;
return;
}
down(i);
ll m = (l + r) / 2;
if (m > ul) update(ul, ur, lc, l, m);
if (m < ur) update(ul, ur, rc, m, r);
up(i);
}
void init(ll n_, ll m_, ll p_[], ll a[]) {
n = n_;
m = m_;
FOR(i, 0, n + m) {
p[i] = p_[i];
if (i) adj[p[i]].pb(i);
}
calc_sub(0);
dfs(0);
FOR(i, n, n + m) {
// cout << i << endl;
adjust(i - n, contrib[i], a[i - n]);
}
}
ll count_ways(ll l, ll r) {
update(l - n, r - n+1);
return st[1].val;
}
// int main() {
// // ll p[7] = {-1, 0, 1, 2, 1, 1, 0};
// // ll a[4] = {1, 0, 1, 0};
// // init(3, 4, p, a);
// // // cout << st[1].val << endl;
// // cout << count_ways(3, 4) << endl;
// // cout << count_ways(4, 5) << endl;
// // cout << count_ways(3, 6) << endl;
// // FOR(i, n, n + m) cout << contrib[i] << endl;
// }