Submission #1011138

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011138		damjandavkov	Digital Circuit (IOI22_circuit)	C++17	100 / 100	780 ms	26320 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll r = 1000002022, p, n;
vector<ll> en, nu, lz, wl, wr;
void upd(int a, int b, int i)
{
    if (wl[i] >= b || wr[i] <= a)
        return;
    if (wl[i] >= a && wr[i] <= b)
    {
        lz[i] ^= 1;
        return;
    }
    upd(a, b, 2 * i);
    upd(a, b, 2 * i + 1);
    nu[i] = en[i] = 0;
    if (lz[2 * i])
    {
        nu[i] += en[2 * i];
        en[i] += nu[2 * i];
    }
    else
    {
        nu[i] += nu[2 * i];
        en[i] += en[2 * i];
    }
    if (lz[2 * i + 1])
    {
        nu[i] += en[2 * i + 1];
        en[i] += nu[2 * i + 1];
    }
    else
    {
        nu[i] += nu[2 * i + 1];
        en[i] += en[2 * i + 1];
    }
}
void init(int N, int M, vector<int> P, vector<int> A)
{
    n = N;
    ll m = M, i, a, b;
    vector<vector<int> > ch(n + m);
    vector<ll> t(n + m), d(n + m), pf, sf;
    for (i = 1; i < n + m; i++)
        ch[P[i]].push_back(i);
    for (i = n; i < n + m; i++)
        t[i] = 1;
    for (i = n - 1; i >= 0; i--)
    {
        t[i] = ch[i].size();
        for (auto h : ch[i])
            t[i] = t[i] * t[h] % r;
    }
    queue<int> q;
    d[0] = 1;
    q.push(0);
    while (!q.empty())
    {
        a = q.front();
        q.pop();
        b = ch[a].size();
        pf.resize(b + 1);
        sf.resize(b + 1);
        pf[0] = sf[b] = 1;
        for (i = 0; i < b; i++)
            pf[i + 1] = pf[i] * t[ch[a][i]] % r;
        for (i = b - 1; i >= 0; i--)
            sf[i] = sf[i + 1] * t[ch[a][i]] % r;
        for (i = 0; i < b; i++)
        {
            d[ch[a][i]] = (pf[i] * sf[i + 1] % r) * d[a] % r;
            q.push(ch[a][i]);
        }
    }
    p = m;
    while (p != (p & -p))
        p++;
    en.resize(2 * p);
    nu.resize(2 * p);
    lz.resize(2 * p);
    wl.resize(2 * p);
    wr.resize(2 * p);
    for (i = p; i < 2 * p; i++)
    {
        nu[i] = 0;
        en[i] = 0;
        if (i < p + m)
        {
            if (A[i - p])
                en[i] = d[i - p + n];
            else
                nu[i] = d[i - p + n];
        }
        lz[i] = 0;
        wl[i] = i;
        wr[i] = i + 1;
    }
    for (i = p - 1; i > 0; i--)
    {
        wl[i] = wl[2 * i];
        wr[i] = wr[2 * i + 1];
        lz[i] = 0;
        nu[i] = nu[2 * i] + nu[2 * i + 1];
        en[i] = en[2 * i] + en[2 * i + 1];
    }
}
int count_ways(int L, int R)
{
    upd(L - n + p, R - n + p + 1, 1);
    if (lz[1])
        return nu[1] % r;
    return en[1] % 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