| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1084124 | tradz | 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 <bits/stdc++.h>
#include "circuit.h"
#define For(i,a,b) for(int i = a; i <= b; i++)
#define Ford(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define RRH(v) v.resize(unique(all(v)) - v.begin())
using namespace std;
const int N = 1e6+7;
const int M = int(1e9) + 2022;
const ll oo = 3e18;
void fadd(int &a, int b) {
a += b;
if (a >= M) a -= M;
}
int add(int x, int y) {
return x + y >= M ? x + y - M : x + y;
}
struct seg {
int N;
vector<int> tree, tot, lazy;
seg() {}
seg(int n, const vector<int>& v, const vector<int>& a) : N(1 << (__lg(n) + 1)), tree(2 * N), tot(2 * N), lazy(2 * N) {
For(i, 0, n - 1) tot[i + N] = v[i], tree[i + N] = v[i] * a[i];
Ford(i, N - 1, 1) {
tot[i] = add(tot[i * 2], tot[i * 2 + 1]);
tree[i] = add(tree[i * 2], tree[i * 2 + 1]);
}
}
void push(int node) {
if (!lazy[node]) return;
tree[node] = tot[node] - tree[node];
if (tree[node] < 0) tree[node] += M;
if (node < N) {
lazy[node * 2] ^= 1;
lazy[node * 2 + 1] ^= 1;
}
lazy[node] = 0;
}
void update(int node, int nl, int nr, int ql, int qr) {
push(node);
if (ql > nr || qr < nl) return;
if (ql <= nl && nr <= qr) {
lazy[node] ^= 1;
push(node);
return;
}
int mid = (nl + nr) / 2;
update(node * 2, nl, mid, ql, qr);
update(node * 2 + 1, mid + 1, nr, ql, qr);
tree[node] = add(tree[node * 2], tree[node * 2 + 1]);
}
} st;
vector<int> p, a, sub, sub2, val;
vector<vector<int>> adj;
int n, m;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N, m = M;
p = P, a = A;
adj.resize(N);
sub.resize(N + M, 1);
sub2.resize(N + M, 1);
For(i, 1, N + M - 1) adj[P[i]].emplace_back(i);
Ford(i, N - 1, 0) {
sub[i] = adj[i].size();
int cur = adj[i].size();
vector<int> pref(cur), suff(cur);
For(j, 0, cur - 1) {
pref[j] = suff[j] = sub[adj[i][j]];
}
For(j, 1, cur - 1) pref[j] = (ll)pref[j - 1] * pref[j] % M;
Ford(j, cur - 2, 0) suff[j] = (ll)suff[j + 1] * suff[j] % M;
For(j, 0, cur - 1) {
int u = adj[i][j];
sub[i] = (ll)sub[i] * sub[u] % M;
sub2[u] = (ll)(j ? pref[j - 1] : 1) * (j + 1 < cur ? suff[j + 1] : 1) % M;
}
}
val.resize(N + M);
val[0] = 1;
For(i, 1, N + M - 1) val[i] = (ll)val[p[i]] * sub2[i] % M;
vector<int> val2(M);
For(i, N, N + M - 1) val2[i - N] = val[i];
st = seg(m, val2, A);
}
int count_ways(int L, int R) {
st.update(1, 0, st.N - 1, L - n, R - n);
return st.tree[1];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#define TASK ""
if (fopen(".inp", "r")) {
freopen(".inp", "r", stdin);
freopen(".out", "w", stdout);
}
if(fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
return 0;
}