Submission #826752

#	Time	Username	Problem	Language	Result	Execution time	Memory
826752		amsraman	Digital Circuit (IOI22_circuit)	C++17	100 / 100	920 ms	31300 KiB

circuit

#include <bits/stdc++.h>

using namespace std;

template <class B>
struct LazySegTree : public B {
    using T_q = typename B::T_q;
    using T_u = typename B::T_u;
    int n, sz, log; vector<T_q> seg; vector<T_u> lazy;
    LazySegTree(int n = 0): n(n), log(__lg(max(n - 1, 1)) + 1) {
        sz = (1 << log), seg.resize(sz << 1, B::e_q), lazy.resize(sz << 1, B::e_u);
    }
    LazySegTree(vector<T_q> & init): n((int) init.size()), log(__lg(max(n - 1, 1)) + 1) {
        sz = (1 << log), seg.resize(sz << 1, B::e_q), lazy.resize(sz << 1, B::e_u);
        copy(init.begin(), init.end(), seg.begin() + sz);
        for(int i = sz - 1; i > 0; i--) refresh(i);
    }
    void refresh(int ind) {
        seg[ind] = B::comb(seg[2 * ind], seg[2 * ind + 1]);
    }
    void app(int ind, int lo, int hi, T_u delta) {
        seg[ind] = B::upd(seg[ind], delta, lo, hi);
        lazy[ind] = B::comb_upd(delta, lazy[ind]);
    }
    void push(int ind, int lo, int hi) {
        if(lo != hi) {
            int mid = (lo + hi) >> 1;
            app(2 * ind, lo, mid, lazy[ind]);
            app(2 * ind + 1, mid + 1, hi, lazy[ind]);
        }
        lazy[ind] = B::e_u;
    }
    void push_from_root(int ind) {
        ind += sz;
        for(int i = log; i > 0; i--) {
            push(ind >> i, (ind >> i << i) - sz, (((ind >> i) + 1) << i) - sz - 1);
        }
    }
    T_q qry(int lo, int hi) {
        push_from_root(lo), push_from_root(hi); T_q ret1 = B::e_q, ret2 = B::e_q;
        for(lo += sz, hi += sz; lo <= hi; lo >>= 1, hi >>= 1) {
            if(lo & 1) ret1 = B::comb(ret1, seg[lo++]);
            if(hi & 1 ^ 1) ret2 = B::comb(seg[hi--], ret2);
        }
        return B::comb(ret1, ret2);
    }
    void upd(int lo, int hi, T_u delta) {
        push_from_root(lo), push_from_root(hi); lo += sz, hi += sz;
        for(int l = lo, r = hi, lvl = 0; l <= r; l >>= 1, r >>= 1, ++lvl) {
            if(l & 1) app(l, (l << lvl) - sz, (l + 1 << lvl) - sz - 1, delta), l++;
            if(r & 1 ^ 1) app(r, (r << lvl) - sz, (r + 1 << lvl) - sz - 1, delta), r--;
        }
        for(int i = 1; i <= log; i++) {
            if(lo >> i << i != lo) refresh(lo >> i);
            if((hi + 1) >> i << i != hi + 1) refresh(hi >> i);
        }
    }
};

const int mod = 1000002022;

struct Monoid {
    using T_q = pair<int, int>; static constexpr T_q e_q = {0, 0};
    using T_u = bool; static const T_u e_u = false;
    T_q comb(T_q a, T_q b) {
        return {(a.first + b.first) % mod, (a.second + b.second) % mod};
    }
    T_q upd(T_q a, T_u b, int l, int r) {
        if(b) {
            return {(a.second - a.first + mod) % mod, a.second};
        }
        return a;
    }
    T_u comb_upd(T_u a, T_u b) {
        // a after b
        return a ^ b;
    }
};

int tot;
LazySegTree<Monoid> lst;

void init(int n, int m, vector<int> p, vector<int> a) {
    tot = n;
    vector<vector<int>> g(n);
    vector<int> prod(n + m, 1);
    vector<pair<int, int>> val(m);
    for(int i = 1; i < n + m; i++) {
        g[p[i]].push_back(i);
    }
    auto dfs = [&](auto rec, int u) -> void {
        prod[u] = (int) g[u].size();
        for(int v: g[u]) {
            if(v < n) {
                rec(rec, v);
                prod[u] = (1LL * prod[u] * prod[v]) % mod;
            }
        }
    };
    auto dfs2 = [&](auto rec, int u, int down) {
        if(u >= n) {
            val[u - n].second = down;
            return;
        }
        int sz = (int) g[u].size(), pf = 1;
        vector<int> sf;
        for(int v: g[u]) sf.push_back(prod[v]);
        sf.push_back(1);
        for(int i = sz - 1; i >= 0; i--) sf[i] = (1LL * sf[i] * sf[i + 1]) % mod;
        for(int i = 0; i < sz; i++) {
            int other = (1LL * pf * sf[i + 1]) % mod;
            rec(rec, g[u][i], (1LL * other * down) % mod);
            pf = (1LL * pf * prod[g[u][i]]) % mod;
        }
    };
    dfs(dfs, 0);
    dfs2(dfs2, 0, 1);
    for(int i = 0; i < m; i++) {
        val[i].first = a[i] * val[i].second;
    }
    lst = LazySegTree<Monoid>(val);
}

int count_ways(int l, int r) {
    lst.upd(l - tot, r - tot, true);
    return lst.seg[1].first;
}

Compilation message (stderr)

circuit.cpp: In instantiation of 'void LazySegTree<B>::upd(int, int, LazySegTree<B>::T_u) [with B = Monoid; LazySegTree<B>::T_u = bool]':
circuit.cpp:125:35:   required from here
circuit.cpp:50:50: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   50 |             if(l & 1) app(l, (l << lvl) - sz, (l + 1 << lvl) - sz - 1, delta), l++;
      |                                                ~~^~~
circuit.cpp:51:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   51 |             if(r & 1 ^ 1) app(r, (r << lvl) - sz, (r + 1 << lvl) - sz - 1, delta), r--;
      |                ~~^~~
circuit.cpp:51:54: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   51 |             if(r & 1 ^ 1) app(r, (r << lvl) - sz, (r + 1 << lvl) - sz - 1, delta), r--;
      |                                                    ~~^~~

• 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