제출 #1255853

#제출 시각아이디문제언어결과실행 시간메모리
1255853biank디지털 회로 (IOI22_circuit)C++17
100 / 100
368 ms35624 KiB
#include <bits/stdc++.h> using namespace std; #define forsn(i, s, n) for (int i = int(s); i < int(n); i++) #define forn(i, n) forsn(i, 0, n) #define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--) #define dforn(i, n) dforsn(i, 0, n) #define sz(x) int(x.size()) #define all(x) begin(x), end(x) using ii = pair<int, int>; using vi = vector<int>; using ll = long long; using vll = vector<ll>; #define fst first #define snd second #define pb push_back #define eb emplace_back const int MAX_N = 2e5 + 9; const int MOD = 1e9 + 2022; int mul(int a, int b) { return 1LL * a * b % MOD; } vi adj[MAX_N]; int val[MAX_N], prod[MAX_N]; int n; void dfs0(int u) { if (u >= n) { val[u] = 1; return; } val[u] = sz(adj[u]); for (int v : adj[u]) { dfs0(v); val[u] = mul(val[u], val[v]); } } void dfs1(int u, int curr) { prod[u] = curr; const int m = sz(adj[u]); vi pref(m + 1), suff(m + 1); pref[0] = 1, suff[m] = 1; forn(i, m) pref[i + 1] = mul(pref[i], val[adj[u][i]]); dforn(i, m) suff[i] = mul(suff[i + 1], val[adj[u][i]]); forn(i, m) dfs1(adj[u][i], mul(mul(curr, pref[i]), suff[i + 1])); } const int SZ = 1 << 18; ii st[2 * SZ]; bool lazy[2 * SZ]; void pass(int u) { if (u < SZ) { lazy[2 * u] ^= lazy[u]; lazy[2 * u + 1] ^= lazy[u]; } if (lazy[u]) swap(st[u].fst, st[u].snd); lazy[u] = false; } void calc(int u) { st[u].fst = st[2 * u].fst + st[2 * u + 1].fst; if (st[u].fst >= MOD) st[u].fst -= MOD; st[u].snd = st[2 * u].snd + st[2 * u + 1].snd; if (st[u].snd >= MOD) st[u].snd -= MOD; } void update(int s, int e, int l = 0, int r = SZ, int u = 1) { pass(u); if (e <= l || r <= s) return; if (s <= l && r <= e) { lazy[u] = true; return pass(u); } int m = (l + r) / 2; update(s, e, l, m, 2 * u); update(s, e, m, r, 2 * u + 1); calc(u); } void init(int N, int M, vi P, vi A) { n = N; forsn(i, 1, N + M) adj[P[i]].pb(i); dfs0(0); dfs1(0, 1); forn(i, M) { st[i + SZ].fst = prod[i + N]; st[i + SZ].snd = 0; if (!A[i]) swap(st[i + SZ].fst, st[i + SZ].snd); } dforsn(i, 1, SZ) calc(i); } int count_ways(int L, int R) { update(L - n, R - n + 1); return st[1].fst; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...