Submission #794552

#	Time	Username	Problem	Language	Result	Execution time	Memory
794552		adrilen	Digital Circuit (IOI22_circuit)	C++17	2 / 100	563 ms	10392 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 max_val = 1;

ll vals[maxn] = { 0 };


void dfs(int p, ll v)
{
    if (!children[p].empty()) vals[p] = v * children[p].size(), max_val *= children[p].size();
    else vals[p] = v;

    fmod(vals[p]);
    fmod(max_val);

    for (int i : children[p]) dfs(i, vals[p]);
}



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);
    }

    dfs(0, 1);

    for (int i = 0; i < m; i++)
    {
        segtree[i + siz][1] = max_val / 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);

    // print();

    return segtree[1][0];
}

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