Submission #794616

#	Time	Username	Problem	Language	Result	Execution time	Memory
794616		adrilen	Digital Circuit (IOI22_circuit)	C++17	100 / 100	932 ms	33264 KiB

circuit

#include "circuit.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<ll, 2>;
using arrr = array<int, 3>;

constexpr ll mod = 1e9 + 2022;
constexpr int maxn = 2e5;

void fmod(ll &val)
{
    if (val >= mod) val %= mod;
}

int n, m;
basic_string <int> children[maxn];


ll subtree[maxn] = { 0 }, vals[maxn];


ll find_subtree_vals(int p)
{
    ll v = children[p].size();
    for (int i : children[p])
    {
        v *= find_subtree_vals(i);
        fmod(v);
    }
    
    subtree[p] = v;
    if (v == 0) subtree[p] = 1;
    return subtree[p];
}



void get_vals(int p)
{
    int g = children[p].size();

    vector<ll> l(g + 1, vals[p]), r(g + 1, 1);



    for (int i = 1; i <= g; i++) {
        l[i] = l[i - 1] * subtree[children[p][i - 1]]; fmod(l[i]);
    }
    
    for (int i = g - 1; i >= 0; i--) {
        r[i] = r[i + 1] * subtree[children[p][i]]; fmod(r[i]);
    }

    // cout << "P" << p << " " << vals[p] << "\n";
    // for (int i : l) cout << i << " ";
    // cout << "\n";
    // for (int i : r) cout << i << " ";
    // cout << "\n";


    for (int i = 0; i < g; i++)
    {
        vals[children[p][i]] = l[i] * r[i + 1];
        fmod(vals[children[p][i]]);
    }

    for (int i : children[p]) get_vals(i);

}

constexpr int siz = 1 << 17;

arr segtree[siz * 2] = { 0 };
bool flipped[siz * 2] = { 0 };

arr merge(arr ap, arr bp)
{
    ap[0] += bp[0], ap[1] += bp[1];
    fmod(ap[0]), fmod(ap[1]);
    return ap;
}

void print()
{
    for (int i = 1; i < 2 * siz; i++)
    {
        if (__builtin_popcount(i) == 1) cout << "\n";
        cout << segtree[i][0] << " ";
    }
    cout << endl;
}


void init(int N, int M, std::vector<int> p, std::vector<int> a) {
    n = N, m = M;


    for (int i = 1; i < n + m; i++)
    {
        children[p[i]].push_back(i);
    }

    find_subtree_vals(0);
    vals[0] = 1;
    get_vals(0);

    // for (int i = 0; i < n + m; i++) cout << subtree[i] << " ";
    // cout << "\n";
    // for (int i = 0; i < n + m; i++) cout << vals[i] << " ";
    // cout << "\n";

    for (int i = 0; i < m; i++)
    {
        segtree[i + siz][1] = vals[i + n]; // Doesn't work with modulo
        if (a[i]) segtree[i + siz][0] = segtree[i + siz][1]; 
    }

    for (int i = siz - 1; i > 0; i--)
    {
        segtree[i] = merge(segtree[i * 2], segtree[i * 2 + 1]);
    }

}

void update(int p, int sl, int sr, int gl, int gr)
{
    if (flipped[p])
    {
        segtree[p][0] = segtree[p][1] - segtree[p][0];
        if (segtree[p][0] < 0) segtree[p][0] += mod;
        

        if (p < siz) flipped[p * 2] ^= 1, flipped[p * 2 + 1] ^= 1;
        flipped[p] ^= 1;
    }

    // cout << p << " " << sl << " " << sr << " " << gl << " " << gr << " \n";

    if (gl <= sl && sr <= gr) {
        segtree[p][0] = segtree[p][1] - segtree[p][0];
        if (segtree[p][0] < 0) segtree[p][0] += mod;


        if (p < siz) flipped[p * 2] ^= 1, flipped[p * 2 + 1] ^= 1;

        return ;
    }


    if (gl > sr || sl > gr) return ;

    int mid = (sl + sr) >> 1;

    update(p * 2, sl, mid, gl, gr);
    update(p * 2 + 1, mid + 1, sr, gl, gr);

    segtree[p] = merge(segtree[p * 2], segtree[p * 2 + 1]);
}



int count_ways(int L, int R) {
    update(1, 0, siz - 1, L - n, R - n);


    return segtree[1][0];
}

• 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