Submission #1212340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212340		Ice_man	Digital Circuit (IOI22_circuit)	C++20	100 / 100	394 ms	33340 KiB

circuit

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <vector>

#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define PB push_back
#define X first
#define Y second
#define mod 1000002022
#define control cout<<"passed"<<endl;




typedef unsigned long long ull;
typedef std::pair <int, int> pii;
typedef long long ll;
typedef std::pair <ll, ll> pll;
typedef std::pair <int, ll> pil;
typedef std::pair <ll, int> pli;
typedef long double ld;


std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}


struct node
{
    ll sum_curr, sum_all;
    bool lamp;
};

node tree[maxn * 4];
ll c[maxn];
bool state[maxn];
int n, m;
std::vector <int> p, a;

void flip(int node)
{
    tree[node].sum_curr = (tree[node].sum_all - tree[node].sum_curr) % mod;
    if(tree[node].sum_curr < 0)
        tree[node].sum_curr += mod;

    tree[node].lamp = !tree[node].lamp;
}

void push_lazy(int node, int l, int r)
{
    if(tree[node].lamp == false)
        return;

    flip(node);
    tree[node].lamp = false;

    if(l != r)
    {
        tree[node * 2].lamp = !tree[node * 2].lamp;
        tree[node * 2 + 1].lamp = !tree[node * 2 + 1].lamp;
    }
}

ll co[maxn];
void build(int node, int l, int r)
{
    if(l == r)
    {
        tree[node].sum_all = co[l] % mod;
        tree[node].sum_curr = (co[l] * state[l]) % mod;
        tree[node].lamp = false;

        return;
    }

    int mid = (l + r) / 2;

    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);

    tree[node].sum_all = tree[node * 2].sum_all + tree[node * 2 + 1].sum_all;
    tree[node].sum_curr = tree[node * 2].sum_curr + tree[node * 2 + 1].sum_curr;

    if(tree[node].sum_all >= mod)
        tree[node].sum_all -= mod;
    if(tree[node].sum_curr >= mod)
        tree[node].sum_curr -= mod;

    tree[node].lamp = false;
}

void update(int node, int l, int r, int ql, int qr)
{
    push_lazy(node, l, r);

    if(ql > r || qr < l)
        return;

    if(l >= ql && r <= qr)
    {
        tree[node].lamp = !tree[node].lamp;
        push_lazy(node, l, r);

        return;
    }

    int mid = (l + r) / 2;

    update(node * 2, l, mid, ql, qr);
    update(node * 2 + 1, mid + 1, r, ql, qr);

    tree[node].sum_curr = tree[node * 2].sum_curr + tree[node * 2 + 1].sum_curr;
    if(tree[node].sum_curr >= mod)
        tree[node].sum_curr -= mod;
}

std::vector <int> v[maxn];
ll ways[maxn];
ll calc[maxn];
ll pref[maxn], suff[maxn];

void dfs(int node)
{
    if(v[node].size() == 0)
    {
        ways[node] = 1;
        return;
    }

    ll cc = 1;
    for(auto& e : v[node])
    {
        dfs(e);
        cc *= ways[e];
        cc %= mod;
    }
    cc *= (int)v[node].size();
    cc %= mod;
    ways[node] = cc;
}

void dfsc(int node)
{
    for(auto& nb : v[node])
    {
        c[nb] = c[node] * calc[nb];
        c[nb] %= mod;

        dfsc(nb);
    }
}

void do_math()
{
    dfs(0);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < v[i].size(); j++)
            pref[j] = suff[j] = ways[v[i][j]];
        for(int j = 1; j < v[i].size(); j++)
            pref[j] = (pref[j - 1] * pref[j]) % mod;
        for(int j = v[i].size() - 2; j >= 0; j--)
            suff[j] = (suff[j + 1] * suff[j]) % mod;

        for(int j = 0 ; j < v[i].size(); j++)
            calc[v[i][j]] = (((j > 0)? pref[j - 1] : 1) * ((j + 1 < v[i].size())? suff[j + 1] : 1)) % mod;
    }
    calc[0] = 1;

    /**for(int i = 0; i < n + m; i++)
        std::cout << calc[i] << " ";
    std::cout << "\n";*/

    c[0] = 1;
    dfsc(0);
}


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

    for(int i = 1; i < n + m; i++)
        v[p[i]].PB(i);
    for(int i = 0; i < m; i++)
        state[i] = a[i];

    do_math();

    for(int i = 0; i < m; i++)
        co[i] = c[n + i];

    /**for(int i = 0; i < m; i++)
        std::cout << co[i] << " ";
    std::cout << "\n";*/

    build(1, 0, m - 1);
}

int count_ways(int l, int r)
{
    l -= n;
    r -= n;
    update(1, 0, m - 1, l, r);
    return (tree[1].sum_curr % mod);
}



/**int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, q;
    std::cin >> n >> m >> q;

    std::vector<int> p;
    p.resize(n + m);
    for (int i = 0; i < n + m; i++)
        std::cin >> p[i];

    std::vector<int> a;
    a.resize(m);
    for (int i = 0; i < m; i++)
        std::cin >> a[i];

    init(n, m, p , a);

    while (q--)
    {
        int l, r;
        std::cin >> l >> r;
        std::cout << count_ways(l, r) << "\n";
    }

    return 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