Submission #800661

#TimeUsernameProblemLanguageResultExecution timeMemory
800661dxz05Digital Circuit (IOI22_circuit)C++17
52 / 100
799 ms24916 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; const int MaxN = 200005; const int MOD = 1e9 + 2022; int N, M; vector<int> A; int contribution[MaxN]; struct node{ int sum; int sum2; bool flag; node(){ sum = sum2 = 0; flag = false; }; }; node tree[4 * MaxN]; void flip(int v){ swap(tree[v].sum, tree[v].sum2); tree[v].flag ^= 1; } void push(int v, int tl, int tr){ if (tl == tr || !tree[v].flag) return; flip(v << 1); flip(v << 1 | 1); tree[v].flag = false; } void build(int v, int tl, int tr){ if (tl == tr){ tree[v].sum = A[tl - N] * contribution[tl]; tree[v].sum2 = (!A[tl - N]) * contribution[tl]; return; } int tm = (tl + tr) >> 1; build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr); tree[v].sum = (tree[v << 1].sum + tree[v << 1 | 1].sum) % MOD; tree[v].sum2 = (tree[v << 1].sum2 + tree[v << 1 | 1].sum2) % MOD; } void update(int v, int tl, int tr, int l, int r){ push(v, tl, tr); if (l <= tl && tr <= r){ flip(v); return; } if (tl > r || tr < l) return; int tm = (tl + tr) >> 1; update(v << 1, tl, tm, l, r); update(v << 1 | 1, tm + 1, tr, l, r); tree[v].sum = (tree[v << 1].sum + tree[v << 1 | 1].sum) % MOD; tree[v].sum2 = (tree[v << 1].sum2 + tree[v << 1 | 1].sum2) % MOD; } void update(int l, int r){ update(1, N, N + M - 1, l, r); } int get(){ return tree[1].sum; } vector<int> g[MaxN]; int dep[MaxN]; void dfs(int v, int p){ for (int u : g[v]){ if (u != p){ dep[u] = dep[v] + 1; dfs(u, v); } } } void init(int _N, int _M, vector<int> P, vector<int> _A) { N = _N, M = _M, A = _A; for (int i = 1; i < N + M; i++){ g[P[i]].push_back(i); } dfs(0, -1); vector<int> pw(N + 1, 1); for (int i = 1; i <= N; i++) pw[i] = pw[i - 1] * 2 % MOD; for (int i = N; i < N + M; i++){ contribution[i] = pw[N - dep[i]]; } build(1, N, N + M - 1); } int count_ways(int L, int R) { update(L, R); return get(); }
#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...