Submission #1218025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218025		moondarkside	Digital Circuit (IOI22_circuit)	C++20	4 / 100	284 ms	17688 KiB

circuit

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

std::vector<long long>VertexWeight;
vector<vector<long long>>Children;
vector<long long> Combinations;
vector<pair<long long, long long>> SegTree;
vector<bool> Inverted;
vector<int> On;
int Nb;


long long GetProductExcept(long long excp,long long n,long long x,long long 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,long long val,long long n,long long x,long long 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(long long l,long long r,long long n,long long x,long long 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(long long enabled,long long mult,long long pos,long long n,long long x,long long 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(long long pos, long long baseMult){
    if(Children[pos].size()==0){
        VertexWeight[pos]=baseMult;
        return;
    }
    if(Children[pos].size()==1){
        AssingWeights(Children[pos][0],baseMult);
        return;
    }
    long long NumChild=Children[pos].size();
    vector<long long> Wmults(4*NumChild,1);
    
    for(long long i=0;i<NumChild;i++){
        Build(Combinations[Children[pos][i]],i,1,0,NumChild+1,Wmults);
    }
    
    for(long long 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){
    Nb=N;
    Combinations=vector<long long>(N+M);
    Children=vector<vector<long long>>(N+M);
    VertexWeight=vector<long long>(N+M);
    
    for(long long i=M+N-1;i>0;i--){
        long long comb=max((long long)1,(long long)Children[i].size());
        for(long long 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));
    On=A;
    for(long long j=0;j<M;j++){
        MakeSegTree(A[j],VertexWeight[j+N],j+N,1,0,N+M+1);
    }
    Nb=N+M+1;
    
}


int count_ways(int L, int R){

    
    return Switch(L,R,1,0,Nb);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11