Submission #1247470

#TimeUsernameProblemLanguageResultExecution timeMemory
1247470m5588ohammedDigital Circuit (IOI22_circuit)C++20
0 / 100
204 ms8584 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; #define mod 1000002022 #define ll long long ll n,m; ll to[200001],tf[200001],ta[200001],cs[200001]; vector <ll> v[200001]; void update_node(ll i){ if(n<i) return; to[i]=(to[i*2]*to[i*2+1]*2)%mod; to[i]+=(tf[i*2]*to[i*2+1])%mod; to[i]+=(to[i*2]*tf[i*2+1])%mod; to[i]%=mod; tf[i]=(ta[i]-to[i]+mod)%mod; //cout<<"UPDATE "<<i<<" "<<tf[i]<<" "<<to[i]<<endl; return; } void flip(ll l1,ll r1,ll i,ll l,ll r){ //cout<<"RANGE "<<l1<<" "<<r1<<" "<<l<<" "<<r<<" "<<i<<endl; if(l1>r||l>r1) return; if(l<=l1&&r1<=r){ //cout<<"FLIP "<<i<<" "<<to[i]<<" "<<tf[i]<<endl; swap(to[i],tf[i]); return; } flip(l1,(l1+r1)/2,i*2,l,r); flip((l1+r1)/2+1,r1,i*2+1,l,r); update_node(i); return; } void build(ll i){ ta[i]=1; if(n<i) return; for(ll j:v[i]){ build(j); ta[i]=(ta[i]*ta[j])%mod; } ta[i]*=(ll)v[i].size(); ta[i]%=mod; //cout<<i<<" "<<ta[i]<<" "<<v[i].size()<<endl; return; } void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N;m=M; for(int i=0;i<m;i++) cs[i+n+1]=A[i]; for(int i=1;i<n+m;i++) v[P[i]+1].push_back(i+1); build(1); for(int i=n+1;i<=n+m;i++){ if(cs[i]==1) to[i]=1; else tf[i]=1; } for(int i=n;i>=1;i--) update_node(i); return; } int count_ways(int L, int R){ flip(0,n,1,L-n+1,R-n+1); return to[1]; } // 3 4 3 // -1 0 1 2 1 1 0 // 1 0 1 0 // 3 4 // 4 5 // 3 6 // 1 7 3 // -1 0 0 0 0 0 0 0 // 1 1 1 1 1 1 1 // 1 1 // 2 2 // 4 7 // 3 4 1 // -1 0 0 1 1 2 2 // 1 1 1 1 // 3 3
#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...