Submission #1029333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029333		vjudge1	Digital Circuit (IOI22_circuit)	C++17	100 / 100	766 ms	36028 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

#define ll long long
#define sz(s) (int)s.size()
#define pb push_back

using namespace std;

const int MAX=2e5+10;
const int mod=1000002022;

int n,m;
vector<int> a;
vector<int> g[MAX];
int c[MAX];

struct segtree{
    int t[4*MAX],s[4*MAX],add[4*MAX];

    void build(int v,int tl,int tr){
        add[v]=0;
        if(tl==tr){
            t[v]=a[tl]*c[tl];
            s[v]=c[tl];
            return;
        }
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=(t[2*v]+t[2*v+1])%mod;
        s[v]=(s[2*v]+s[2*v+1])%mod;
    }

    void upd(int v){
        add[v]^=1;
        t[v]=(s[v]-t[v]+mod)%mod;
    }

    void push(int v){
        if(add[v]){
            upd(2*v);
            upd(2*v+1);
            add[v]=0;
        }
    }

    void update(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            upd(v);
            return;
        }
        int tm=(tl+tr)/2;
        push(v);
        update(2*v,tl,tm,l,r);
        update(2*v+1,tm+1,tr,l,r);
        t[v]=(t[2*v]+t[2*v+1])%mod;
        s[v]=(s[2*v]+s[2*v+1])%mod;
    }
}T;

int pr[MAX];

void calc(int v){
    pr[v]=sz(g[v]);
    if(g[v].empty())pr[v]=1;
    for(auto to:g[v]){
        calc(to);
        pr[v]=pr[v]*1ll*pr[to]%mod;
    }
}


void dfs(int v,int s){
    if(g[v].empty()){
        c[v-n]=s;
        return;
    }
    vector<int> pref(sz(g[v]),0),suf(sz(g[v]),0);
    pref[0]=pr[g[v][0]];
    for(int i=1;i<sz(g[v]);i++){
        pref[i]=pref[i-1]*1ll*pr[g[v][i]]%mod;
    }
    suf[sz(g[v])-1]=pr[g[v][sz(g[v])-1]];
    for(int i=sz(g[v])-2;i>=0;i--){
        suf[i]=suf[i+1]*1ll*pr[g[v][i]]%mod;
    }
    for(int i=0;i<sz(g[v]);i++){
        int to=g[v][i];
        int f=s*1ll*(i-1>=0?pref[i-1]:1)%mod*(i+1<sz(g[v])?suf[i+1]:1)%mod;
        dfs(to,f);
    }
}

void init(int N, int M,vector<int> P,vector<int> A) {
    n=N;
    m=M;
    a=A;
    for(int i=1;i<N+M;i++){
        g[P[i]].pb(i);
    }
    calc(0);
    dfs(0,1);
    T.build(1,0,M-1);
}

int count_ways(int L, int R){
    L-=n;
    R-=n;
    // cout<<L<<" "<<R<<"\n";
    T.update(1,0,m-1,L,R);
    return T.t[1];
}

• 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