제출 #1162421

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1162421		The_Samurai	디지털 회로 (IOI22_circuit)	C++17	16 / 100	296 ms	5788 KiB

circuit

#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
const int mod = 1'000'002'022;

struct lazy {
    struct node {
        ll one, zero;
        bool lazy;

        node() {
            one = zero = 0;
            lazy = false;
        }

        void merge(const node &a, const node &b) {
            one = (a.one * b.one * 2 + a.one * b.zero + a.zero * b.one) % mod;
            zero = (a.zero * b.zero * 2 + a.one * b.zero + a.zero * b.one) % mod;
        }

        void impact() {
            swap(one, zero);
            lazy = !lazy;
        }

        void propagate(node &a, node &b) {
            if (lazy) {
                a.impact();
                b.impact();
                lazy = false;
            }
        }
    };

    vector<node> tree;
    int size;
    node neutral_element;

    void build(const vector<int> &a) {
        size = 1;
        while (size < a.size()) size *= 2;
        tree.assign(2 * size - 1, neutral_element);
        for (int i = size - 1; i < size - 1 + a.size(); i++) {
            if (a[i - size + 1]) tree[i].one = 1;
            else tree[i].zero = 1;
        }
        for (int i = size - 2; i >= 0; i--) {
            tree[i].merge(tree[i * 2 + 1], tree[i * 2 + 2]);
            // cout << i << ' ' << tree[i].one << ' ' << tree[i].zero << endl;
        }
    }

    void upd(int l, int r, int x, int lx, int rx) {
        if (lx >= r or l >= rx) return;
        if (l <= lx and rx <= r) {
            tree[x].impact();
            return;
        }
        tree[x].propagate(tree[2 * x + 1], tree[2 * x + 2]);
        int mid = (lx + rx) >> 1;
        upd(l, r, 2 * x + 1, lx, mid);
        upd(l, r, 2 * x + 2, mid, rx);
        tree[x].merge(tree[2 * x + 1], tree[2 * x + 2]);
    }

    void upd(int l, int r) {
        upd(l, r + 1, 0, 0, size);
    }

    node get(int l, int r, int x, int lx, int rx) {
        if (lx >= r or l >= rx) return neutral_element;
        if (l <= lx and rx <= r) return tree[x];
        tree[x].propagate(tree[2 * x + 1], tree[2 * x + 2]);
        int mid = (lx + rx) >> 1;
        node ans;
        ans.merge(get(l, r, 2 * x + 1, lx, mid), get(l, r, 2 * x + 2, mid, rx));
        return ans;
    }

    int get(int l, int r) {
        return get(l, r + 1, 0, 0, size).one;
    }
};

void upd(ll &a, ll b) {
    a = (a + b) % mod;
    if (a < 0) a += mod;
}

int n, m;
vector<int> a, p;
lazy sg;

void init(int _n, int _m, std::vector<int> P, std::vector<int> A) {
    n = _n, m = _m;
    a = A; p = P;
    sg.build(a);
    // cout << '\t' << sg.get(0, m - 1) << endl;
}

int count_ways(int L, int R) {
    sg.upd(L - n, R - n);
    return sg.get(0, m - 1);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11