Submission #630041

#	Time	Username	Problem	Language	Result	Execution time	Memory
630041		qwerasdfzxcl	Digital Circuit (IOI22_circuit)	C++17	46 / 100	1295 ms	40264 KiB

circuit

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

using namespace std;
typedef long long ll;
const int MOD = 1'000'002'022;
vector<int> adj[100100];
int n, m, a[800800];

struct Seg1{
    ll tree[800800], sz;
    void init(int n){
        sz = n;
        for (int i=sz;i<sz*2;i++) tree[i] = adj[i-sz].size();
        for (int i=sz-1;i;i--) tree[i] = tree[i<<1] * tree[i<<1|1] % MOD;
    }
    void update(int p, int x){
        for (tree[p+=sz]=x;p>1;p>>=1) tree[p>>1] = tree[p] * tree[p^1] % MOD;
    }
}tree1;

struct Seg2{
    pair<ll, ll> tree[800800];
    int lazy[800800];
    pair<ll, ll> combine(pair<ll, ll> x, pair<ll, ll> y){return {(x.first + y.first)%MOD, (x.second + y.second)%MOD};}
    void init(int i, int l, int r){
        lazy[i] = 0;
        if (l==r) {tree[i] = {0, a[l]}; return;}
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
    void propagate(int i, int l, int r){
        if (!lazy[i]) return;
        swap(tree[i].first, tree[i].second);
        if (l!=r){
            lazy[i<<1] ^= 1;
            lazy[i<<1|1] ^= 1;
        }
        lazy[i] = 0;
    }
    void update(int i, int l, int r, int s, int e){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] ^= 1;
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e); update(i<<1|1, m+1, r, s, e);
        tree[i] = combine(tree[i<<1], tree[i<<1|1]);
    }
}tree2;

void dfs(int s){
    if (s<=n) tree1.update(s, 1);
    else a[s-n] = tree1.tree[1];

    for (auto &v:adj[s]) dfs(v);

    if (s<=n) tree1.update(s, adj[s].size());
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    adj[0].push_back(0);
    n = N, m = M;

    for (int i=1;i<n+m;i++){
        adj[P[i]+1].push_back(i+1);
    }

    tree1.init(n+1);
    dfs(1);
    tree2.init(1, 1, m);

    for (int i=0;i<m;i++) if (A[i]) tree2.update(1, 1, m, i+1, i+1);
}

int count_ways(int L, int R) {
    tree2.update(1, 1, m, L-n+1, R-n+1);
    return tree2.tree[1].first;
}

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