Submission #1057410

#TimeUsernameProblemLanguageResultExecution timeMemory
1057410sofijavelkovskaDigital Circuit (IOI22_circuit)C++17
50 / 100
3095 ms35712 KiB
#include "circuit.h" //#include "stub.cpp" #include <bits/stdc++.h> using namespace std; const int MOD=1000002022, MAXN=(1<<18); int n, m; vector<int> parent, a; vector<int> adj[MAXN]; int subtree[2*MAXN]; long long factor[2*MAXN]; long long ones[2*MAXN-1], zeros[2*MAXN-1]; int lazy[2*MAXN-1]={0}; long long power(long long n, long long k) { long long result=1, mul=n; for (int i=0; i<32; i++) { if (k&(1<<i)) result=result*mul%MOD; mul=mul*mul%MOD; } return result; } void calcsize(int x) { if (x>=n) subtree[x]=0; else subtree[x]=1; for (auto y : adj[x]) { calcsize(y); subtree[x]=subtree[x]+subtree[y]; } return; } void calcfactor(int x, long long current) { if (x>=n) return; int l=adj[x][0]; int r=adj[x][1]; factor[l]=current*power(2, subtree[r])%MOD; factor[r]=current*power(2, subtree[l])%MOD; calcfactor(l, factor[l]); calcfactor(r, factor[r]); return; } void propagate(int x, int l, int r) { if (r-l==1) { lazy[x]=0; return; } if (lazy[x]==0) return; swap(ones[2*x+1], zeros[2*x+1]); swap(ones[2*x+2], zeros[2*x+2]); lazy[2*x+1]=(lazy[2*x+1]+1)%2; lazy[2*x+2]=(lazy[2*x+2]+1)%2; lazy[x]=0; return; } void update(int x, int l, int r, int lt, int rt) { if (l>=rt || r<=lt) return; if (l>=lt && r<=rt) { swap(ones[x], zeros[x]); lazy[x]=(lazy[x]+1)%2; return; } propagate(x, l, r); update(2*x+1, l, (l+r)/2, lt, rt); update(2*x+2, (l+r)/2, r, lt, rt); ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD; zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD; return; } void buildtree(int x, int l, int r) { if (r-l==1) { if (l>=m) { ones[x]=0; zeros[x]=0; return; } if (a[l]==1) { ones[x]=factor[l+n]; zeros[x]=0; } else { ones[x]=0; zeros[x]=factor[l+n]; } return; } buildtree(2*x+1, l, (l+r)/2); buildtree(2*x+2, (l+r)/2, r); ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD; zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD; return; } void init(int N, int M, vector<int> P, vector<int> A) { n=N; m=M; parent=P; a=A; for (int i=1; i<n+m; i++) adj[parent[i]].push_back(i); calcsize(0); calcfactor(0, 1); buildtree(0, 0, MAXN); return; } int count_ways(int l, int r) { l=l-n; r=r-n; update(0, 0, MAXN, l, r+1); return ones[0]; }
#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...