Submission #1235917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235917		Sir_Ahmed_Imran	Digital Circuit (IOI22_circuit)	C++17	2 / 100	3071 ms	5680 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define mid ((s + e) / 2)
#define rc (2 * v + 1)
#define lc (2 * v)

const int mod = 1000002022;

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

int mul(int a, int b){
    return (1ll * a * b) % mod;
}

int n, m;
int p[MAXN];
int q[MAXN];
int dp[MAXN];
int val[MAXN];
vector<int> z;
int lazy[4 * MAXN];
vector<int> a[MAXN];
int seg[4 * MAXN][2];

void built(int v = 1, int s = 0, int e = m){
    if(e - s == 1){
        seg[v][z[s]] = val[s + n];
        return;
    }
    built(lc, s, mid);
    built(rc, mid, e);
    seg[v][0] = add(seg[lc][0], seg[rc][0]);
    seg[v][1] = add(seg[lc][1], seg[rc][1]);
}

void push(int v){
    if(lazy[v] % 2)
        swap(seg[v][0], seg[v][1]);
    if(rc < 4 * MAXN){
        lazy[rc] += lazy[v];
        lazy[lc] += lazy[v];
    }
    lazy[v] = 0;
}

void update(int l, int r, int v = 1, int s = 0, int e = m){
    push(v);
    if(r <= s || e <= l) return;
    if(l <= s && e <= r){
        lazy[v]++;
        push(v);
        return;
    }
    update(l, r, lc, s, mid);
    update(l, r, rc, mid, e);
    seg[v][0] = add(seg[lc][0], seg[rc][0]);
    seg[v][1] = add(seg[lc][1], seg[rc][1]);
}

void dfs(int v){
    dp[v] = 1;
    for(auto & u : a[v]){
        dfs(u);
        p[u] = dp[v];
        dp[v] = mul(dp[v], dp[u]);
    }
    if(!a[v].empty())
        dp[v] = mul(dp[v], a[v].size());
    reverse(all(a[v]));
    int x = 1;
    for(auto & u : a[v]){
        dfs(u);
        q[u] = x;
        x = mul(x, dp[u]);
        val[u] = mul(p[u], q[u]);
    }
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M, z = A;
    for(int i = 1; i < P.size(); i++)
        a[P[i]].append(i);
    dfs(0);
    for(int i = val[0] = 1; i < P.size(); i++)
        val[i] = mul(val[i], val[P[i]]);
    built();
}

int count_ways(int l, int r){
    update(l - n, r - n + 1);
    return seg[1][1];
}

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