oj.uz

Submission #934072

# Submission time Handle Problem Language Result Execution time Memory
934072 2024-02-26T18:42:16 Z jamesbamber Digital Circuit (IOI22_circuit) C++17
4 / 100
 621 ms 20976 KB 
#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(8*(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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 600 KB 5th lines differ - on the 1st token, expected: '481', found: '506'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 3rd lines differ - on the 1st token, expected: '133738288', found: '824438726'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 600 KB 5th lines differ - on the 1st token, expected: '481', found: '506'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 10556 KB Output is correct
2 Correct 601 ms 20976 KB Output is correct
3 Correct 621 ms 20824 KB Output is correct
4 Correct 608 ms 20908 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 10556 KB Output is correct
2 Correct 601 ms 20976 KB Output is correct
3 Correct 621 ms 20824 KB Output is correct
4 Correct 608 ms 20908 KB Output is correct
5 Incorrect 488 ms 10556 KB 3rd lines differ - on the 1st token, expected: '249436868', found: '812217068'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 344 KB 3rd lines differ - on the 1st token, expected: '133738288', found: '824438726'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 600 KB 5th lines differ - on the 1st token, expected: '481', found: '506'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 1 ms 600 KB 5th lines differ - on the 1st token, expected: '481', found: '506'
4 Halted 0 ms 0 KB -