Submission #736329

#	Time	Username	Problem	Language	Result	Execution time	Memory
736329		puppy	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1315 ms	45496 KiB

circuit

#include "circuit.h"

#include <vector>
#include <functional>
#include <cmath>
#include <iostream>
using ll = long long;
using namespace std;
//모든 인덱스에 1씩 더하기
int par[200005];
ll tot[200005];
ll dp[200005];
vector<int> g[200005];
vector<int> prf[200005], suf[200005];
const ll mod = 1'000'002'022;
ll ans = 0;
namespace {
    int N, M;
}
//A[i]: N+1+i의 상태
struct sumseg
{
    vector<ll> tree, lazy;
    void setup(int n)
    {
        int sz = 1 << ((int)ceil(log2(n+1))+1);
        tree.resize(sz); lazy.resize(sz, 1);
    }
    int init(int s, int e, int node, vector<ll> &arr)
    {
        if (s == e) return tree[node] = arr[s];
        else return tree[node] = (init(s, (s+e)/2, 2*node, arr) + init((s+e)/2+1, e, 2*node+1, arr)) % mod;
    }
    void propagate(int s, int e, int node)
    {
        tree[node] *= lazy[node];
        if (s != e) {
            lazy[2*node] *= lazy[node];
            lazy[2*node+1] *= lazy[node];
        }
        lazy[node] = 1;
    }
    void upd(int s, int e, int node, int l, int r)
    {
        propagate(s, e, node);
        if (e < l || r < s) return;
        if (l <= s && e <= r) {
            lazy[node] *= -1;
            propagate(s, e, node);
            return;
        }
        upd(s, (s+e)/2, 2*node, l, r);
        upd((s+e)/2+1, e, 2*node+1, l, r);
        tree[node] = (tree[2*node] + tree[2*node+1]) % mod;
    }
    int query(int s, int e, int node, int l, int r)
    {
        propagate(s, e, node);
        if (e < l || r < s) return 0;
        if (l <= s && e <= r) return tree[node];
        return (query(s, (s+e)/2, 2*node, l, r) + query((s+e)/2+1, e, 2*node+1, l, r)) % mod;
    }
}seg;
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
    ::N = N;
    ::M = M;
    seg.setup(M);
    par[1] = 0;
    for (int i = 1; i < N + M; i++) {
        par[i+1] = P[i] + 1;
    }
    for (int i = 2; i <= N + M; i++) g[par[i]].push_back(i);
    function<void(int)> dfs = [&](int v)
    {
        if (v <= N) {
            tot[v] = g[v].size();
            for (int j:g[v]) {
                dfs(j);
                tot[v] = tot[v] * tot[j] % mod;
            }
        }
        else {
            tot[v] = 1;
        }
    };
    dfs(1);
    function<void(int)> dfs2 = [&](int v)
    {
        if (v > N) return;
        for (int j:g[v]) dfs2(j);
        prf[v].resize(g[v].size());
        suf[v].resize(g[v].size());
        prf[v][0] = tot[g[v][0]];
        suf[v].back() = tot[g[v].back()];
        for (int i = 1; i < (int)prf[v].size(); i++) {
            prf[v][i] = prf[v][i-1] * tot[g[v][i]] % mod;
        }
        for (int i = (int)suf[v].size() - 2; i >= 0; i--) {
            suf[v][i] = suf[v][i+1] * tot[g[v][i]] % mod;
        }
    };
    dfs2(1);
    dp[1] = 1;
    function<void(int)> dfs3 = [&](int v)
    {
        for (int j = 0; j < (int)g[v].size(); j++) {
            ll mul = 1;
            if (j >= 1) mul = mul * prf[v][j-1] % mod;
            if (j <= (int)g[v].size() - 2) mul = mul * suf[v][j+1] % mod;
            dp[g[v][j]] = dp[v] * mul % mod;
            dfs3(g[v][j]);
        }
    };
    dfs3(1);
    for (int i = N + 1; i <= N + M; i++) ans = (ans + A[i-N-1] * dp[i]) % mod;
    vector<ll> st(M);
    for (int i = N + 1; i <= N + M; i++) {
        st[i-N-1] = A[i-N-1] == 1 ? -dp[i] : dp[i];
    }
    seg.init(0, M-1, 1, st);
}

int count_ways(int L, int R) {
    int l = L - N, r = R - N;
    ans += seg.query(0, M-1, 1, l, r);
    seg.upd(0, M-1, 1, l, r);
    ans = (ans % mod + mod) % mod;
    return ans;
}

• 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