Submission #1084125

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084125		tradz	Digital Circuit (IOI22_circuit)	C++17	0 / 100	470 ms	5732 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
#define For(i,a,b) for(int i = a; i <= b; i++)
#define Ford(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define RRH(v) v.resize(unique(all(v)) - v.begin())
 
using namespace std;
 
const int mod = int(1e9) + 2022;
const ll oo = 3e18;
 
void fadd(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
 
int add(int x, int y) {
    return x + y >= mod ? x + y - mod : x + y;
}
 
struct seg {
    int N; 
    vector<int> tree, tot, lazy;
 
    seg() {}
 
    seg(int n, const vector<int>& v, const vector<int>& a) : N(1 << (__lg(n) + 1)), tree(2 * N), tot(2 * N), lazy(2 * N) {
        For(i, 0, n - 1) tot[i + N] = v[i], tree[i + N] = v[i] * a[i];
        Ford(i, N - 1, 1) {
            tot[i] = add(tot[i * 2], tot[i * 2 + 1]);
            tree[i] = add(tree[i * 2], tree[i * 2 + 1]);
        }
    }
 
    void push(int node) {
        if (!lazy[node]) return;
        tree[node] = tot[node] - tree[node];
        if (tree[node] < 0) tree[node] += mod;
        if (node < N) {
            lazy[node * 2] ^= 1;
            lazy[node * 2 + 1] ^= 1;
        }
        lazy[node] = 0;
    }
 
    void update(int node, int nl, int nr, int ql, int qr) {
        push(node);
        if (ql > nr || qr < nl) return;
        if (ql <= nl && nr <= qr) {
            lazy[node] ^= 1;
            push(node);
            return;
        }
        int mid = (nl + nr) / 2;
        update(node * 2, nl, mid, ql, qr);
        update(node * 2 + 1, mid + 1, nr, ql, qr);
        tree[node] = add(tree[node * 2], tree[node * 2 + 1]);
    }
} st;
 
vector<int> p, a, sub, sub2, val;
vector<vector<int>> adj;
int n, m;
 
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N, m = M;
    p = P, a = A;
    adj.resize(N);
    sub.resize(N + M, 1);
    sub2.resize(N + M, 1);
    
    For(i, 1, N + M - 1) adj[P[i]].emplace_back(i);
    
    Ford(i, N - 1, 0) {
        sub[i] = adj[i].size();
        int cur = adj[i].size();
        vector<int> pref(cur), suff(cur);
        
        For(j, 0, cur - 1) {
            pref[j] = suff[j] = sub[adj[i][j]];
        }
 
        For(j, 1, cur - 1) pref[j] = (ll)pref[j - 1] * pref[j] % M;
        Ford(j, cur - 2, 0) suff[j] = (ll)suff[j + 1] * suff[j] % M;
 
        For(j, 0, cur - 1) {
            int u = adj[i][j];
            sub[i] = (ll)sub[i] * sub[u] % M;
            sub2[u] = (ll)(j ? pref[j - 1] : 1) * (j + 1 < cur ? suff[j + 1] : 1) % M;
        }
    }
 
    val.resize(N + M);
    val[0] = 1;
    
    For(i, 1, N + M - 1) val[i] = (ll)val[p[i]] * sub2[i] % M;
 
    vector<int> val2(M);
    For(i, N, N + M - 1) val2[i - N] = val[i];
    st = seg(m, val2, A);
}
 
int count_ways(int L, int R) {
    st.update(1, 0, st.N - 1, L - n, R - n);
    return st.tree[1];
}
 

• Subtask 1: 0 / 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