Submission #759384

#TimeUsernameProblemLanguageResultExecution timeMemory
759384amunduzbaevDigital Circuit (IOI22_circuit)C++17
18 / 100
785 ms8192 KiB
#include "circuit.h" #include "bits/stdc++.h" using namespace std; #ifndef EVAL #include "stub.cpp" #endif #define ar array typedef long long ll; const int N = 1e3 + 5; const int mod = 1'000'002'022; int N_; //~ struct ST{ //~ ar<int, 2> tree[N << 2]; //~ int c[N << 2]; //~ ST(){ //~ memset(tree, 0, sizeof tree); //~ memset(c, 0, sizeof c); //~ } //~ void push(int x, int lx, int rx){ //~ if(lx == rx) return; //~ if(c[x]){ //~ swap(tree[x << 1][0], tree[x << 1 | 1][0]); //~ swap(tree[x << 1][1], tree[x << 1 | 1][1]); //~ c[x << 1] ^= 1, c[x << 1 | 1] ^= 1; //~ } //~ c[x] = 0; //~ } //~ void set(int i, int v, int lx, int rx, int x){ //~ if(lx == rx){ //~ tree[x][0] = v; //~ return; //~ } //~ push(x, lx, rx); //~ int m = (lx + rx) >> 1; //~ if(i <= m) set(i, v, lx, m, x << 1); //~ else set(i, v, m + 1, rx, x << 1 | 1); //~ tree[x][0] = (tree[x << 1][0] + tree[x << 1 | 1][0]) % mod; //~ tree[x][1] = (tree[x << 1][1] + tree[x << 1 | 1][1]) % mod; //~ } //~ void set(int i, int v){ //~ set(i, v, 0, N, 1); //~ } //~ void togl(int l, int r, int lx, int rx, int x){ //~ if(lx > r || rx < l) return; //~ if(lx >= l && rx <= r){ //~ c[x] ^= 1; //~ swap(tree[x][0], tree[x][1]); //~ return; //~ } //~ int m = (lx + rx) >> 1; //~ push(x, lx, rx); //~ togl(l, r, lx, m, x << 1); //~ togl(l, r, m + 1, rx, x << 1 | 1); //~ tree[x][0] = (tree[x << 1][0] + tree[x << 1 | 1][0]) % mod; //~ tree[x][1] = (tree[x << 1][1] + tree[x << 1 | 1][1]) % mod; //~ } //~ void togl(int l, int r){ //~ togl(l, r, 0, N, 1); //~ } //~ }tree; struct ST{ int a[N], c[N]; ST(){ memset(a, 0, sizeof a); memset(c, 0, sizeof c); } void set(int i, int v){ a[i] = v; } void togl(int l, int r){ for(int i=l;i<=r;i++){ c[i] ^= 1; } } int get(){ int res = 0; for(int i=0;i<N;i++){ if(c[i]){ res = (res + a[i]) % mod; } } return res; } }tree; void init(int n, int m, vector<int> p, vector<int> a) { vector<vector<int>> edges(n + m); for(int i=1;i<n+m;i++){ edges[p[i]].push_back(i); } vector<int> dp(n + m), up(n + m); function<void(int)> dfs = [&](int u){ dp[u] = max(1, (int)edges[u].size()); for(auto x : edges[u]){ dfs(x); dp[u] = dp[u] * 1ll * dp[x] % mod; } }; dfs(0); //~ for(int i=0;i<n+m;i++){ //~ cout<<dp[i]<<" "; //~ } //~ cout<<"\n"; function<void(int)> re = [&](int u){ int pref = 1; vector<int> suff(edges[u].size() + 1); suff.back() = 1; for(int i=(int)edges[u].size() - 1;~i;i--){ suff[i] = suff[i + 1] * 1ll * dp[edges[u][i]] % mod; } for(int i=0;i<(int)edges[u].size();i++){ up[edges[u][i]] = up[u] * 1ll * suff[i + 1] % mod * 1ll * pref % mod; pref = pref * 1ll * dp[edges[u][i]] % mod; re(edges[u][i]); } }; up[0] = 1; re(0); for(int i=n;i<n+m;i++){ tree.set(i - n, up[i]); //~ if(a[i - n]) tree.togl(i - n, i - n); } for(int i=n;i<n+m;i++){ if(a[i - n]) tree.togl(i - n, i - n); } N_ = n; } int count_ways(int l, int r) { l -= N_, r -= N_; tree.togl(l, r); return tree.get(); //~ return tree.tree[1][1]; //~ cout<<tree.tree[1]<<"\n"; }
#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...