Submission #934077

#	Time	Username	Problem	Language	Result	Execution time	Memory
934077		jamesbamber	Digital Circuit (IOI22_circuit)	C++17	100 / 100	711 ms	42900 KiB

circuit

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

using ll = long long;
constexpr ll MOD = 1'000'002'022;

struct segment{
    struct Node{
        ll sum=0, act=0, lazy=0;
    };

    vector<Node> tr;

    void push(int v){
        if(!tr[v].lazy) return;
        tr[v].lazy = 0;
        if(2*v+1 < (int)tr.size()){
            tr[2*v].lazy ^= 1;
            tr[2*v+1].lazy ^= 1;
        }
        tr[v].act = (MOD + tr[v].sum - tr[v].act)%MOD;
    }

    void merge(int v){
        tr[v].sum = (tr[2*v].sum + tr[2*v+1].sum)%MOD;
        tr[v].act = (tr[2*v].act + tr[2*v+1].act)%MOD;
    }

    void build(int v, int l, int r, vector<ll> &a){
        if(r-l == 1){
            tr[v] = {a[l], a[l], 0};
            return;
        }
        int m = (l+r)/2;
        build(2*v, l, m, a);
        build(2*v+1, m, r, a);
        merge(v);
    }

    segment(int n, vector<ll> &v){
        tr.resize(4*(n+1));
        build(1, 0, n, v);
    }

    void upd(int v, int l, int r, int ql, int qr){
        push(v);
        if(l >= qr or r <= ql) return;
        if(l >= ql and r <= qr){
            tr[v].lazy = 1;
            push(v);
            return;
        }
        int m = (l+r)/2;
        upd(2*v, l, m, ql, qr);
        upd(2*v+1, m, r, ql, qr);
        merge(v);
    }

    ll query(){
        return tr[1].act;
    }
};

segment *st;
int m, n;

void init(int N, int M, std::vector<int> P, std::vector<int> A){

    vector<vector<int>> ad(N+M);
    for(int i=1; i<N+M; i++){
        ad[P[i]].push_back(i);
    }
    vector<ll> prod(N+M);
    vector<ll> ways(M);

    function<void(int)> dfs = [&](int v){
        prod[v] = max(1, (int)ad[v].size());
        for(int u: ad[v]){
            dfs(u);
            prod[v] = prod[v]*prod[u]%MOD;
        }
    };

    function<void(int,ll)> dfs2 = [&](int v, ll up){
        if(v >= N){
            ways[v-N] = up;
            return;
        }
        int len = ad[v].size();
        vector<ll> pref(len+1, 1), suff(len+1, 1);
        for(int i=0; i<len; i++) pref[i+1] = pref[i]*prod[ad[v][i]]%MOD;
        for(int i=len-1; i>=0; i--) suff[i] = suff[i+1]*prod[ad[v][i]]%MOD;

        for(int i=0; i<len; i++){
            dfs2(ad[v][i], pref[i]*suff[i+1]%MOD*up%MOD);
        }
    };

    dfs(0); dfs2(0, 1);

    m = M; n = N;
    st = new segment(m, ways);
    for(int i=0; i<M; i++){
        if(!A[i]) st->upd(1, 0, m, i, i+1);
    }
}

int count_ways(int L, int R) {
    st->upd(1, 0, m, L-n, R+1-n);
    return st->query();
}

• 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