Submission #1217712

#TimeUsernameProblemLanguageResultExecution timeMemory
1217712moondarksideDigital Circuit (IOI22_circuit)C++20
0 / 100
194 ms8732 KiB
#include <iostream> #include<bits/stdc++.h> using namespace std; std::vector<long long>VertexWeight; vector<vector<int>>Children; vector<long long> Combinations; vector<pair<long long, long long>> SegTree; vector<bool> Inverted; int GetProductExcept(int excp,int n,int x,int y,vector<long long>& Wmults){ if(y>excp && x>excp){ return Wmults[n]; } if(y<excp && x<excp){ return Wmults[n]; } if(y==excp && x==excp){ return 1; } return (GetProductExcept(excp,n*2+1,(y+x)/2+1,y,Wmults)*GetProductExcept(excp,n*2,x,(y+x)/2,Wmults))%1000002022; } void Build(long long mult,int val,int n,int x,int y,vector<long long>& Wmults){ if(y>val && x>val){ return; } if(y<val && x<val){ return; } if(x==y && x==val){ Wmults[n]=(Wmults[n]*mult)%1000002022; return; } Wmults[n]=(Wmults[n]*mult)%1000002022; Build(mult,val,n*2,x,(y+x)/2,Wmults); Build(mult,val,n*2+1,(y+x)/2+1,y,Wmults); return; } long long Switch(int l,int r,int n,int x,int y){ if(x>r){ return SegTree[n].second; } if(l>y){ return SegTree[n].second; } if(x>=l && y<=r){ Inverted[n]=!Inverted[n]; SegTree[n]={SegTree[n].first,((SegTree[n].first-SegTree[n].second)%1000002022+1000002022)%1000002022}; return SegTree[n].second; } if(Inverted[n]){ SegTree[n*2]={SegTree[n*2].first,((SegTree[n*2].first-SegTree[n*2].second)%1000002022+1000002022)%1000002022}; SegTree[n*2+1]={SegTree[n*2+1].first,((SegTree[n*2+1].first-SegTree[n*2+1].second)%1000002022+1000002022)%1000002022}; Inverted[n]=false; } long long vala=Switch(l,r,n*2,x,(y+x)/2); long long valb=Switch(l,r,n*2+1,(y+x)/2+1,y); long long val=(vala+valb)%1000002022; SegTree[n]={SegTree[n].first,val}; return val; } void MakeSegTree(int enabled,long long mult,int pos,int n,int x,int y){ if(y>=pos && pos>=x){ SegTree[n]={(SegTree[n].first+mult)%1000002022,(SegTree[n].second+mult*enabled)%1000002022}; } if(pos>y){ return; } if(pos<x){ return; } if(x!=y){ MakeSegTree(enabled,mult,pos,2*n,x,(x+y)/2); MakeSegTree(enabled,mult,pos,2*n+1,(x+y)/2+1,y); } return; } void AssingWeights(int pos, int baseMult){ if(Children[pos].size()==0){ VertexWeight[pos]=baseMult; return; } if(Children[pos].size()==1){ AssingWeights(Children[pos][0],baseMult); return; } int NumChild=Children[pos].size(); vector<long long> Wmults(4*NumChild,1); for(int i=0;i<NumChild;i++){ Build(Combinations[Children[pos][i]],i,1,0,NumChild+1,Wmults); } for(int i=0;i<NumChild;i++){ long long extraMult=(GetProductExcept(i,1,0,NumChild+1,Wmults)*baseMult)%1000002022; AssingWeights(Children[pos][i],extraMult); } } void init(int N, int M, vector<int> P, vector<int> A){ Combinations=vector<long long>(N+M); Children=vector<vector<int>>(N+M); VertexWeight=vector<long long>(N+M); for(int i=M+N-1;i>0;i--){ long long comb=max((long long)1,(long long)Children[i].size()); for(int j=0;j<Children[i].size();j++){ comb=(comb*Combinations[Children[i][j]])%1000002022; } Combinations[i]=comb; Children[P[i]].push_back(i); } AssingWeights(0,1); SegTree=vector<pair<long long,long long>>(4*(M+N)); Inverted=vector<bool>(4*(M+N)); for(int j=0;j<M;j++){ MakeSegTree(A[j],VertexWeight[j+N],j+N,1,0,N+M+1); } } int count_ways(int L, int R){ return Switch(L,R,1,0,Children.size()+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...