Submission #1239857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239857		matsakyannn	Digital Circuit (IOI22_circuit)	C++20	100 / 100	372 ms	50488 KiB

circuit

#include <bits/stdc++.h>
using namespace std;

#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x << ' '; print(x); cerr << endl;
#else
#define dbg(x)
#endif 

void print(int x) {cerr << x;}
void print(long long x) {cerr << x;}
void print(char x) {cerr << x;}
void print(string x) {cerr << x;}
void print(double x) {cerr << x;}
template <class T> void print(vector <T> x);
template <class T> void print(set <T> x);
template <class T> void print(multiset <T> x);
template <class T, class V> void print(pair <T, V> x);
template <class T, class V> void print(map <T, V> x);
template <class T> void print(vector <T> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
template <class T> void print(set <T> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
template <class T> void print(multiset <T> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}
template <class T, class V> void print(pair <T, V> x) {cerr << "{"; print(x.first); cerr << ' '; print(x.second); cerr << "}";}
template <class T, class V> void print(map <T, V> x) {cerr << "[ "; for(auto i : x) {print(i); cerr << ' ';} cerr << "]";}

#define ll long long
#define pb push_back
#define ppb pop_back
#define PII pair <int, int>
#define PLL pair <ll, ll>
#define all(v) (v).begin(), (v).end()
#define OK cerr << "OK\n";
#define MP make_pair

const ll mod = 1000002022;
const int NN = 3e5 + 5;
vector <int> T[NN];
vector <int> p, a;
int n, m;
ll gorcakic[NN], allCases[NN];
vector <ll> pref, suff;

void calc_allCases(int node){
    if(T[node].empty()){
        allCases[node] = 1;
        return;
    }
    int sz = T[node].size();
    for(int i = 0; i < sz; i++){
        int u = T[node][i];
        calc_allCases(u);
    }
    pref.clear(); pref.resize(sz + 2);
    suff.clear(); suff.resize(sz + 2);
    pref[0] = suff[sz + 1] = 1;
    for(int i = 0; i < sz; i++){
        int u = T[node][i];
        pref[i + 1] = pref[i] * allCases[u];
        pref[i + 1] %= mod;
    }
    for(int i = sz - 1; i >= 0; i--){
        int u = T[node][i];
        suff[i + 1] = suff[i + 2] * allCases[u];
        suff[i + 1] %= mod;
    }
    allCases[node] = sz * pref[sz]; 
    allCases[node] %= mod;
}

void dfs(int node, ll tomultiply){
    if(T[node].empty()){
        gorcakic[node] = tomultiply;
        return;
    }
    int sz = T[node].size();
    pref.clear(); pref.resize(sz + 2);
    suff.clear(); suff.resize(sz + 2);
    pref[0] = suff[sz + 1] = 1;
    for(int i = 0; i < sz; i++){
        int u = T[node][i];
        pref[i + 1] = pref[i] * allCases[u];
        pref[i + 1] %= mod;
    }
    for(int i = sz - 1; i >= 0; i--){
        int u = T[node][i];
        suff[i + 1] = suff[i + 2] * allCases[u];
        suff[i + 1] %= mod;
    }
    vector <ll> val(sz);
    for(int i = 0; i < sz; i++){
        val[i] = pref[i] * suff[i + 2];
        val[i] %= mod;
        val[i] *= tomultiply;
        val[i] %= mod;
    }
    for(int i = 0; i < sz; i++){
        dfs(T[node][i], val[i]);
    }
}


struct segtree{
    int sz = 1;
    pair <ll, int> tree[4 * NN];
    ll sum[NN];
 
    void init(){
        while(sz < m) sz <<= 1;
        sum[0] = 0;
        for(int i = 1; i <= m; i++){
            sum[i] = sum[i - 1] + gorcakic[i + n - 1];
            sum[i] %= mod;
        }
        build(0, 0, sz);
    }
 
    void build(int x, int lx, int rx){
        if(rx == lx + 1){
            tree[x].first = a[lx] * gorcakic[lx + n];
            tree[x].first %= mod;
            tree[x].second = 0;
            return;
        }
 
        int mx = (lx + rx) / 2;
        build(2 * x + 1, lx, mx);
        build(2 * x + 2, mx, rx);
        tree[x].first = tree[2 * x + 1].first + tree[2 * x + 2].first;
        tree[x].first %= mod;
        tree[x].second = 0;
    }
 
    void propagate(int x, int lx, int rx){
        if(rx == lx + 1 || tree[x].second % 2 == 0) return;
        int mx = (lx + rx) / 2;
        tree[2 * x + 1].second += tree[x].second;
        tree[2 * x + 2].second += tree[x].second;
        tree[x].second = 0;
        tree[2 * x + 1].first = (sum[mx] - sum[lx]) - tree[2 * x + 1].first; tree[2 * x + 1].first %= mod;
        tree[2 * x + 2].first = (sum[rx] - sum[mx]) - tree[2 * x + 2].first; tree[2 * x + 2].first %= mod;
    }
 
    void upd(int l, int r){
        upd(l, r, 0, 0, sz);
    }
 
    void upd(int l, int r, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(lx >= r || rx <= l) return;
        if(lx >= l && rx <= r){
            tree[x].first = (sum[rx] - sum[lx]) - tree[x].first;
            tree[x].first %= mod;
            tree[x].second = 1;
            return;
        }
 
        int mx = (lx + rx) / 2;
        upd(l, r, 2 * x + 1, lx, mx);
        upd(l, r, 2 * x + 2, mx, rx);
        tree[x].first = tree[2 * x + 1].first + tree[2 * x + 2].first;
        tree[x].first %= mod;
    }
} st;

void init(int N, int M, std::vector<int> P, std::vector<int> A){
    n = N, m = M, p = P, a = A;
    for(int i = 1; i < n + m; i++){
        T[p[i]].pb(i);
    }
    calc_allCases(0);
    dfs(0, 1);
    st.init();
}

int count_ways(int L, int R){
    st.upd(L - n, R - n + 1);
    return (st.tree[0].first + mod) % mod;
}

• 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