Submission #630222

#	Time	Username	Problem	Language	Result	Execution time	Memory
630222		talant117408	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1136 ms	42972 KiB

circuit

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

#ifndef EVAL
#include "stub.cpp"
#endif

using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
#define PI                  2*acos(0.0)

const ll mod = 1000002022;

ll add(ll a, ll b) {
    return ((a + b) % mod + mod) % mod;
}

ll mult(ll a, ll b) {
    return ((a * b) % mod + mod) % mod;
}

const int N = 2e5 + 7;
ll tree[2][N * 4], lz[N * 4]; // 0 - all configurations; 1 - valid configurations;
vector <int> graph[N];
vector <ll> pref[N], suff[N];
int n, m;
vector <int> parent, state;
ll valid_for[N], ans_for[N];

ll dfs(int v) {
    valid_for[v] = max(1, sz(graph[v]));
    for (auto to : graph[v]) {
        valid_for[v] = mult(valid_for[v], dfs(to));
    }
    return valid_for[v];
}

void calc(int v, ll val) {
    ans_for[v] = val;
    for (int i = 0; i < sz(graph[v]); i++) {
        auto to = graph[v][i];
        calc(to, mult(val, mult((i == 0 ? 1ll : pref[v][i - 1]), (i == sz(graph[v]) - 1ll ? 1 : suff[v][i + 1]))));
    }
}

void build(int v, int l, int r) {
    if (l == r) {
        tree[0][v] = ans_for[l + n];
        if (state[l]) {
            tree[1][v] = ans_for[l + n];
        }
        return;
    }
    int mid = (l + r) >> 1;
    build(v * 2, l, mid);
    build(v * 2 + 1, mid + 1, r);
    tree[0][v] = add(tree[0][v * 2], tree[0][v * 2 + 1]);
    tree[1][v] = add(tree[1][v * 2], tree[1][v * 2 + 1]);
}

void push(int v, int l, int r) {
    if (lz[v]) {
        tree[1][v] = add(tree[0][v], -tree[1][v]);
        if (l != r) {
            lz[v * 2] ^= lz[v];
            lz[v * 2 + 1] ^= lz[v];
        }
        lz[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) {
        lz[v] ^= 1;
        push(v, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(v * 2, l, mid, ql, qr);
    update(v * 2 + 1, mid + 1, r, ql, qr);
    tree[1][v] = add(tree[1][v * 2], tree[1][v * 2 + 1]);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N, m = M, parent = P, state = A;
    for (int i = 1; i < n + m; i++) {
        graph[parent[i]].pb(i);
    }
    dfs(0);
    for (int i = 0; i < n + m; i++) {
        for (auto to : graph[i]) {
            pref[i].pb(valid_for[to]);
            suff[i].pb(valid_for[to]);
        }
        for (int j = 1; j < sz(pref[i]); j++) {
            pref[i][j] = mult(pref[i][j], pref[i][j - 1]);
        }
        for (int j = sz(suff[i]) - 2; j >= 0; j--) {
            suff[i][j] = mult(suff[i][j], suff[i][j + 1]);
        }
    }
    calc(0, 1);
    build(1, 0, m - 1);
}

int count_ways(int L, int R) {
    update(1, 0, m - 1, L - n, R - n);
    return tree[1][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