Submission #627557

#	Time	Username	Problem	Language	Result	Execution time	Memory
627557		Tigerpants	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1136 ms	39448 KiB

circuit

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>

using namespace std;

typedef long long int ll;
typedef vector<int> stdvi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;

const ll big_mod = 1000002022;

ll N;
ll M;
vi A;
vi P;

vvi Q;

vpi segtree;
vpi left_right;
vb lazy;

pi combine(pi a, pi b) {
    return make_pair( (a.first + b.first) % big_mod, (a.second + b.second) % big_mod);
}

pi flip(pi a) {
    return make_pair( (big_mod + a.second - a.first) % big_mod, a.second);
}

void lazy_propagation(int x) {
    if (lazy[x]) {
        segtree[x] = flip(segtree[x]);
        lazy[x] = false;
        if (left_right[x].first != left_right[x].second) {
            lazy[2 * x] = !lazy[2 * x];
            lazy[2 * x + 1] = !lazy[2 * x + 1];
        }
    }
}

void update(int x, int l, int r) { // flip all in the interval [l, r]
    lazy_propagation(x);
    if ((left_right[x].first > r) || (l > left_right[x].second)) {
        return;
    }
    if ((l <= left_right[x].first) && (left_right[x].second <= r)) {
        lazy[x] = true;
        lazy_propagation(x);
        return;
    }
    update(2 * x, l, r);
    update(2 * x + 1, l, r);
    segtree[x] = combine(segtree[2 * x], segtree[2 * x + 1]);
}

pi query(int x, int l, int r) {
    lazy_propagation(x);
    if ((left_right[x].first > r) || (l > left_right[x].second)) {
        return make_pair((ll)0, (ll)0);
    }
    if ((l <= left_right[x].first) && (left_right[x].second <= r)) {
        return segtree[x];
    }
    return combine(query(2 * x, l, r), query(2 * x + 1, l, r));
}

vi B;

void build(int x, int l, int r) {
    left_right[x] = make_pair(l, r);
    lazy[x] = false;
    if (l == r) {
        segtree[x] = make_pair(A[l] * B[l], B[l]);
        return;
    }
    int m = (l + r) /  2;
    build(2 * x, l, m);
    build(2 * x + 1, m + 1, r);
    segtree[x] = combine(segtree[2 * x], segtree[2 * x + 1]);
}

vi dp;

ll calc_dp(int cur) {

    if (cur >= N) {
        return (ll)1;
    }
    
    ll n = (ll)Q[cur].size();

    if (n == 1) {
        dp[Q[cur][0]] = 1;
        return calc_dp(Q[cur][0]);
    }

    vi children(n);
    for (int i = 0; i < n; i++) {
        children[i] = calc_dp(Q[cur][i]);
    }

    vi left(n);
    vi right(n);

    left[0] = children[0];
    right[n - 1] = children[n - 1];

    for (int i = 1; i < n; i++) {
        left[i] = (left[i - 1] * children[i]) % big_mod;
        right[n - 1 - i] = (right[n - i] * children[n - 1 - i]) % big_mod;
    }

    dp[Q[cur][0]] = right[1];
    for (int i = 1; i < n - 1; i++) {
        dp[Q[cur][i]] = (left[i - 1] * right[i + 1]) % big_mod;
    }
    dp[Q[cur][n - 1]] = left[n - 2];

    return (right[0] * n) % big_mod;
}

void calc_delta(int cur, ll product_above) {
    product_above *= dp[cur];
    product_above %= big_mod;

    if (cur >= N) {
        B[cur - N] = product_above;
        return;
    }

    for (vi::iterator child = Q[cur].begin(); child != Q[cur].end(); child++) {
        calc_delta(*child, product_above);
    }
}

void init(int N_, int M_, stdvi P_, stdvi A_) {
    N = N_;
    M = M_;

    //cout << "one" << endl;

    A.resize(M);
    for (int i = 0; i < M; i++) {
        A[i] = (ll)A_[i];
    }

    //cout << "two" << endl;
    P.resize(N + M);
    for (int i = 0; i < N + M; i++) {
        P[i] = (ll)P_[i];
    }

    //cout << "three" << endl;
    Q.resize(N);
    for (int i = 1; i < N + M; i++) {
        Q[P[i]].push_back(i);
    }

    //cout << "four" << endl;
    B.resize(M);
    // now we install B[i] with the delta which node N + i inflicts upon the root...

    //cout << "five" << endl;
    dp.resize(N + M);
    calc_dp(0);
    dp[0] = 1;

    /*
    for (auto t : dp) {
        cout << t << " ";
    }
    cout << endl;
    */

    calc_delta(0, 1);

    /*
    for (auto t : B) {
        cout << t << " ";
    }
    cout << endl;
    */

    segtree.resize(4 * M);
    left_right.resize(4 * M);
    lazy.resize(4 * M);

    build(1, 0, M - 1);

    /*
    for (int i = 0; i < segtree.size(); i++) {
        cout << "(" << segtree[i].first << ", " << segtree[i].second << " : " << left_right[i].first << ", " << left_right[i].second << " " << lazy[i] << ") ";
    }
    cout << endl;
    for (auto t : segtree) {
        cout << "(" << t.first << ", " << t.second << ") ";
    }
    cout << endl;
    */
}

int count_ways(int L, int R) {
    update(1, L - N, R - N);

    /*
    for (int i = 0; i < segtree.size(); i++) {
        cout << "(" << segtree[i].first << ", " << segtree[i].second << " : " << left_right[i].first << ", " << left_right[i].second << " " << lazy[i] << ") ";
    }
    cout << endl;
    for (auto t : segtree) {
        cout << "(" << t.first << ", " << t.second << ") ";
    }
    cout << endl;
    */

    return (int)query(1, 0, M - 1).first;
}

/*
int main() {

    int N_ = 3;
    int M_ = 4;
    stdvi P_ = {-1, 0, 1, 2, 1, 1, 0};
    stdvi A_ = {1, 0, 1, 0};

    int N_ = 1;
    int M_ = 100;
    stdvi P_ = {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    stdvi A_ = {1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0};
    init(N_, M_, P_, A_);
    //cout << count_ways(3, 4) << endl;
    //cout << count_ways(4, 5) << endl;
    cout << count_ways(0, 76) << endl;
    cout << count_ways(2, 54) << endl;
    cout << count_ways(1, 101) << endl;
    cout << count_ways(49, 80) << endl;
    cout << count_ways(79, 79) << endl;
}
*/

• 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