Submission #634515

#	Time	Username	Problem	Language	Result	Execution time	Memory
634515		mosiashvililuka	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1373 ms	29288 KiB

circuit

#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,msh[200009],f[200009],K[800009],mod=1000002022LL,pas,DP[200009],DP2[200009],DP3[200009],jm[800009],seg[800009],seg2[800009],l,r,z,za;
vector <long long> v[200009];
void dfs(long long q, long long w){
    if(v[q].size()==0){
        DP[q]=1;
        return;
    }
    DP[q]=v[q].size();
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfs((*it),q);
        DP[q]*=DP[(*it)];DP[q]%=mod;
    }
    zx=1;
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        DP2[(*it)]=zx;
        zx*=DP[(*it)];zx%=mod;
    }
    vector <long long>::iterator it=v[q].end();it--;
    zx=1;
    while(1){
        DP2[(*it)]*=zx;DP2[(*it)]%=mod;
        zx*=DP[(*it)];zx%=mod;
        if(it==v[q].begin()) break;
        it--;
    }
}
void dfs2(int q, int w){
    DP3[q]*=DP2[q];DP3[q]%=mod;
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        DP3[(*it)]=DP3[q];
        dfs2((*it),q);
    }
}
void bld(long long q, long long w, long long rr){
    if(q==w){
        if(f[q]==1){
            seg[rr]=K[q];
        }
        return;
    }
    bld(q,(q+w)/2,rr*2);
    bld((q+w)/2+1,w,rr*2+1);
    seg[rr]=seg[rr*2]+seg[rr*2+1];seg[rr]%=mod;
}
void init(int NN, int MM, std::vector<int> PP, std::vector<int> AA) {
    a=NN+MM;
    for(i=1; i<a; i++){
        msh[i+1]=PP[i]+1;
        v[msh[i+1]].push_back(i+1);
    }
    for(i=NN+1; i<=a; i++){
        f[i]=AA[i-NN-1];
    }
    DP2[1]=1;DP3[1]=1;
    dfs(1,0);
    dfs2(1,0);
    for(i=NN+1; i<=a; i++){
        K[i]=DP3[i];
    }
    za=1;
    while(za<a) za*=2;
    for(i=1; i<=za; i++){
        jm[i]=jm[i-1]+K[i];jm[i]%=mod;
    }
    bld(1,za,1);
}
void pushdown(long long q, long long w, long long rr){
    if(q!=w){
        seg2[rr*2]^=seg2[rr];
        seg2[rr*2+1]^=seg2[rr];
    }
    if(seg2[rr]!=0){
        seg[rr]=(jm[w]-jm[q-1]+mod)-seg[rr]+mod;
        seg[rr]%=mod;
    }
    seg2[rr]=0;
}
void upd(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]=z;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    seg[rr]=seg[rr*2]+seg[rr*2+1];seg[rr]%=mod;
}
void read(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z+=seg[rr];z%=mod;
        return;
    }
    read(q,(q+w)/2,rr*2);
    read((q+w)/2+1,w,rr*2+1);
}
int count_ways(int L, int R) {
    L++;R++;
    l=L;r=R;z=1;
    upd(1,za,1);
    pushdown(1,za,1);
    l=1;r=a;z=0;
    read(1,za,1);
    return z;
}

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