Submission #1237366

#TimeUsernameProblemLanguageResultExecution timeMemory
1237366RakhimovAmirDigital Circuit (IOI22_circuit)C++20
16 / 100
472 ms20636 KiB
#include "circuit.h" #include<bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000002022; vector<vector<int>> v; vector<vector<ll>> d; vector<vector<ll>> d2; vector<int> A, pr, psh; int N, M; void build(int x, int tl, int tr) { if (tl == tr) { d[x][A[tl - N]] = 1; d[x][A[tl - N] ^ 1] = 0; d2[x][A[tl - N]] = 0; d2[x][A[tl - N] ^ 1] = 1; // cout << x << " " << d[x][A[tl - N]] << " " << d2[x][A[tl - N] ^ 1] << "\n"; return; } int lft = 2 * x + 1, rgh = 2 * x + 2; int tm = (tl + tr) / 2; build(lft, tl, tm); build(rgh, tm + 1, tr); d[x][0] = ((((d[lft][0] * d[rgh][0]) % MOD) * 2 % MOD) + (d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD) % MOD; d[x][1] = ((d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD + (d[lft][1] * d[rgh][1] % MOD) * 2 % MOD) % MOD; d2[x][0] = (((d2[lft][0] * d2[rgh][0]) % MOD) * 2 % MOD + (d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD) % MOD; d2[x][1] = ((d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD + (d2[lft][1] * d2[rgh][1] % MOD) * 2 % MOD) % MOD; } void upd(int x, int tl, int tr, int L, int R) { if (R < tl || L > tr) return; if (L <= tl && R >= tr) { psh[x] ^= 1; swap(d[x][0], d2[x][0]); swap(d[x][1], d2[x][1]); return; } int lft = 2 * x + 1, rgh = 2 * x + 2; if (psh[x]) { psh[x] = 0; psh[lft] ^= 1; psh[rgh] ^= 1; swap(d[lft][0], d2[lft][0]); swap(d[lft][1], d2[lft][1]); swap(d[rgh][0], d2[rgh][0]); swap(d[rgh][1], d2[rgh][1]); } int tm = (tl + tr) / 2; upd(lft, tl, tm, L, R); upd(rgh, tm + 1, tr, L, R); d[x][0] = ((((d[lft][0] * d[rgh][0]) % MOD) * 2 % MOD) + (d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD) % MOD; d[x][1] = ((d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD + (d[lft][1] * d[rgh][1] % MOD) * 2 % MOD) % MOD; d2[x][0] = (((d2[lft][0] * d2[rgh][0]) % MOD) * 2 % MOD + (d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD) % MOD; d2[x][1] = ((d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD + (d2[lft][1] * d2[rgh][1] % MOD) * 2 % MOD) % MOD; } void init(int N, int M, vector<int> P, vector<int> A) { pr.resize(N + M); v.resize(N + M); d.resize(N + M); d2.resize(N + M); psh.resize(N + M); ::A = A; ::N = N; ::M = M; for (int i = 0; i < N + M; i++) { d[i].resize(2); d2[i].resize(2); psh[i] = 0; } build(0, N, N + M - 1); } int count_ways(int L, int R) { upd(0, N, N + M - 1, L, R); return d[0][1]; }
#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...