Submission #1227144

#TimeUsernameProblemLanguageResultExecution timeMemory
1227144brintonDigital Circuit (IOI22_circuit)C++20
46 / 100
3057 ms7704 KiB
#include "circuit.h" // #include "stub.cpp" #include <bits/stdc++.h> #define MOD 1000002022 using namespace std; struct SEG{ private: struct Node{ long long sum,val; bool flip; Node(){} Node(long long isum){ sum = isum,flip = false,val = 0; } }; vector<Node> tree; vector<long long> mul; int N; void init(int l,int r,int idx){ if(l == r){ tree[idx] = Node(mul[l]); return; } int m = (l+r)/2; init(l,m,idx*2); init(m+1,r,idx*2+1); tree[idx] = Node((tree[idx*2].sum+tree[idx*2+1].sum)%MOD); } void flip(int l,int r,int idx,int L,int R){ if(l == L && r == R){ tree[idx].val = (tree[idx].sum-tree[idx].val+MOD)%MOD; tree[idx].flip = !tree[idx].flip; return; } // push tag down if(tree[idx].flip){ tree[idx*2].val = (tree[idx*2].sum-tree[idx*2].val+MOD)%MOD; tree[idx*2+1].val = (tree[idx*2+1].sum-tree[idx*2+1].val+MOD)%MOD; tree[idx*2].flip = !tree[idx*2].flip; tree[idx*2+1].flip = !tree[idx*2+1].flip; tree[idx].flip = false; } int m = (l+r)/2; if(R <= m){ flip(l,m,idx*2,L,R); }else if(L >= m+1){ flip(m+1,r,idx*2+1,L,R); }else{ flip(l,m,idx*2,L,m); flip(m+1,r,idx*2+1,m+1,R); } tree[idx].val = (tree[idx*2].val+tree[idx*2+1].val)%MOD;// only val change; } public: SEG(){} SEG(vector<long long> imul){ mul = imul; N = mul.size(); tree.resize(4*N+5); init(0,N-1,1); } long long getAns(){ return tree[1].val; } void flip(int l,int r){ flip(0,N-1,1,l,r); } }; vector<vector<int>> child; vector<long long> tot; vector<long long> mul; int N,M; vector<int> A; SEG seg; void init(int iN, int iM, vector<int> P, vector<int> iA) { N = iN,M = iM; A = iA; child.resize(N); for(int i = 1;i < P.size();i++){ child[P[i]].push_back(i); } tot = vector<long long>(N+M,1); for(int i = N-1;i >= 0;i--){ tot[i] = child[i].size(); for(auto c:child[i]){ tot[i] = tot[i]*tot[c]%MOD; } } mul.resize(M); function<void(int,long long)> dfs = [&](int cur,long long cval){ if(cur >= N){ mul[cur-N] = cval; return; } vector<long long> suf; for(auto nxt:child[cur]){ suf.push_back(tot[nxt]); } for(int i = suf.size()-2;i >= 0;i--) suf[i] = suf[i]*suf[i+1]%MOD; long long pref = 1; for(int i = 0;i < child[cur].size();i++){ int nxt = child[cur][i]; if(i+1 < child[cur].size()) dfs(nxt,cval*pref%MOD*suf[i+1]%MOD); else dfs(nxt,cval*pref%MOD); pref = pref*tot[nxt]%MOD; } }; dfs(0,1LL); for(int i = 0;i < M;i++) seg = SEG(mul); for(int i = 0;i < M;i++) if(A[i]) seg.flip(i,i); // for(auto &i:mul) cout << i << " ";cout << endl; } int count_ways(int L, int R) { L -= N, R -= N; seg.flip(L,R); return seg.getAns(); } /* 62: precalculate size, multiply it, range flip */
#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...