Submission #1228770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228770		ericl23302	디지털 회로 (IOI22_circuit)	C++20	16 / 100	360 ms	5112 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1000002022;

int n, m;
vector<pair<ll, ll>> segTree(2e5 + 5, {0, 0});
vector<bool> lazy(2e5 + 5, false);

pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b) {
    pair<ll, ll> res = {0, 0};
    (res.first += (2 * a.first * b.first)) %= MOD;
    (res.first += (a.first * b.second + a.second * b.first)) %= MOD;
    (res.second += (a.first * b.second + a.second * b.first)) %= MOD;
    (res.second += (2 * a.second * b.second)) %= MOD;
    return res;
}

void push_down(int cur, int treeLeft, int treeRight) {
    if (!lazy[cur]) return;
    swap(segTree[cur].first, segTree[cur].second);
    lazy[cur] = false;
    if (treeLeft == treeRight) return;
    lazy[cur * 2 + 1] = !lazy[cur * 2 + 1];
    lazy[cur * 2 + 2] = !lazy[cur * 2 + 2];
}

void setup(int cur, int treeLeft, int treeRight, int pos, pair<ll, ll> val) {
    if (pos < treeLeft || pos > treeRight) return;
    if (treeLeft == treeRight) {
        segTree[cur] = val;
        return;
    }
    int mid = (treeLeft + treeRight) / 2;
    setup(cur * 2 + 1, treeLeft, mid, pos, val);
    setup(cur * 2 + 2, mid + 1, treeRight, pos, val);
    segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
}

void update(int cur, int treeLeft, int treeRight, int qLeft, int qRight) {
    push_down(cur, treeLeft, treeRight);
    if (qRight < treeLeft || qLeft > treeRight) return;
    if (treeLeft >= qLeft && treeRight <= qRight) {
        lazy[cur] = true;
        push_down(cur, treeLeft, treeRight);
        return;
    }
    int mid = (treeLeft + treeRight) / 2;
    update(cur * 2 + 1, treeLeft, mid, qLeft, qRight);
    update(cur * 2 + 2, mid + 1, treeRight, qLeft, qRight);
    segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N; 
    m = M;
    for (int i = 0; i < M; ++i) {
        if (A[i]) setup(0, 1, M, i + 1, {0, 1});
        else setup(0, 1, M, i + 1, {1, 0});
    }
    // for (int i = 0; i < n + m + 2; ++i) cout << segTree[i].first << ' ' << segTree[i].second << ' ' << lazy[i] << "   ";
    // cout << endl;
}

int count_ways(int L, int R) {
    update(0, 1, m, L - n + 1, R - n + 1);
    // for (int i = 0; i < n + m + 2; ++i) cout << segTree[i].first << ' ' << segTree[i].second << ' ' << lazy[i] << "   ";
    // cout << endl;
    return segTree[0].second;
}

• 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