Submission #1230982

#TimeUsernameProblemLanguageResultExecution timeMemory
1230982MalixDigital Circuit (IOI22_circuit)C++20
100 / 100
381 ms39156 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1000002022; int n,m,k; vi a,p,lazy; vector<ll> X,Y,Z,ch; vector<vector<ll>> pref,suff; vii ed; void dfs(int x,ll y){ if(ed[x].empty()){ Z[x-n]=y; return; } REP(i,0,ed[x].size()){ ll q=1,r=1; if(i!=0)q=pref[x][i-1]; if(i!=ed[x].size()-1)r=suff[x][i+1]; dfs(ed[x][i],(((y*q)%M)*r)%M); } } void build(int x,int l,int r){ if(l==r){ if(a[l])X[x]=Z[l]; else Y[x]=Z[l]; return; } int mid=(l+r)/2; build(2*x,l,mid); build(2*x+1,mid+1,r); X[x]=(X[2*x]+X[2*x+1])%M; Y[x]=(Y[2*x]+Y[2*x+1])%M; } void update(int x,int l,int r,int u,int v){ if(u>v)return; if(lazy[x]%2){ lazy[x]=0; if(l!=r){ swap(X[2*x],Y[2*x]); swap(X[2*x+1],Y[2*x+1]); lazy[2*x]++; lazy[2*x+1]++; } } if(l==u&&r==v){ swap(X[x],Y[x]); lazy[x]++; return; } int mid=(l+r)/2; update(2*x,l,mid,u,min(v,mid)); update(2*x+1,mid+1,r,max(u,mid+1),v); X[x]=(X[2*x]+X[2*x+1])%M; Y[x]=(Y[2*x]+Y[2*x+1])%M; } void init(int N, int MM, std::vector<int> P, std::vector<int> A) { n=N;m=MM;p=P;a=A; k=n+m; X.resize(4*m+1,0); Y.resize(4*m+1,0); Z.resize(m,0); lazy.resize(4*m+1,0); ed.resize(n+m); ch.resize(n+m,0); REP(i,1,n+m)ed[p[i]].PB(i); REP(i,1,n+m)ch[p[i]]++; REP(i,n,n+m)ch[i]=1; for(int i=n-1;i>=1;i--){ ch[p[i]]*=ch[i]; ch[p[i]]%=M; } pref.resize(n);suff.resize(n); REP(i,0,n){ int sz=ed[i].size(); pref[i].resize(sz); suff[i].resize(sz); REP(j,0,sz){ pref[i][j]=ch[ed[i][j]]; suff[i][j]=ch[ed[i][j]]; } REP(j,1,sz){ pref[i][j]*=pref[i][j-1]; pref[i][j]%=M; } for(int j=sz-2;j>=0;j--){ suff[i][j]*=suff[i][j+1]; suff[i][j]%=M; } } dfs(0,1LL); build(1,0,m-1); return; } int count_ways(int L, int R) { update(1,0,m-1,L-n,R-n); return X[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...