Submission #1058027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058027		dozer	Digital Circuit (IOI22_circuit)	C++17	7 / 100	331 ms	13912 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define LL node * 2
#define RR node * 2 + 1
#define ll long long
#define MAXN 100005

const int modulo = 1000002022;
const ll INF = 2e18 + 7;

int add(ll a, ll b){
    if (a + b < modulo) return a + b;
    return a + b - modulo;
}

int subs(ll a, ll b){
    if (a < b) return a - b + modulo;
    return a - b;
}

int mul(ll a, ll b){
    return (a * b) % modulo;
}

int fe(ll a, ll b){
    if (b == 0) return 1;
    if (b % 2) return mul(a, fe(a, b - 1));
    int tmp = fe(a, b / 2);
    return mul(tmp, tmp);
}


struct SegTree{
    vector<int> t, lazy, arr, sum;
    int n;

    void build(int node, int l, int r){
        if (l == r){
            sum[node] = arr[l];
            t[node] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(LL, l, mid);
        build(RR, mid + 1, r);
        sum[node] = add(sum[LL], sum[RR]);
        t[node] = 0;
    }

    void push(int node, int l, int r){
        if (lazy[node] == 0) return;
        t[node] = subs(sum[node], t[node]);
        lazy[node] = 0;
        if (l != r) lazy[LL] ^= 1, lazy[RR] ^= 1;
    }

    void update(int node, int l, int r, int sl, int sr){
        push(node, l, r);
        if (l > sr || r < sl) return;
        if (l >= sl && r <= sr){
            lazy[node] ^= 1;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(LL, l, mid, sl, sr);
        update(RR, mid + 1, r, sl, sr);
        t[node] = add(t[LL], t[RR]);
    }


    int query(int node, int l, int r, int sl, int sr){
        push(node, l, r);
        if (l > sr || r < sl) return 0;
        if (l >= sl && r <= sr) return t[node];
        int mid = (l + r) / 2;
        return add(query(LL, l, mid, sl, sr), query(RR, mid + 1, r, sl, sr));
    }


    SegTree(int N, vector<int> a){
        n = N;
        t.resize(4 * n + 5, 0), lazy.resize(4 * n + 5, 0), sum.resize(4 * n + 5, 0);
        arr = a;
        build(1, 0, n - 1);
    }
};

vector<int> adj[MAXN];
int val[MAXN], sz[MAXN], n, m;

void dfs(int node){
    sz[node] = 0;
    if (node < n) sz[node]++;
    for (auto i : adj[node]){
        dfs(i);
        sz[node] += sz[i];
    }
}


void dfs2(int node, int x){
    val[node] = x;
    if (adj[node].empty()) return;
    else if (adj[node].size() == 2){
        int l = adj[node][0], r = adj[node][1];
        dfs2(l, mul(x, fe(2, sz[r])));
        dfs2(r, mul(x, fe(2, sz[l])));
    }
}


SegTree *T;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    n = N, m = M;
    for (int i = 1; i < n + m; i++)
        adj[P[i]].pb(i);

    dfs(0);
    dfs2(0, 1);

    vector<int> arr(m);
    for (int i = 0; i < m; i++) arr[i] = val[i + n];
        
    T = new SegTree(m, arr);
    for (int i = 0; i < m; i++) 
        if (A[i]) T->update(1, 0, m - 1, i, i);
}

int count_ways(int L, int R) {
    T->update(1, 0, m - 1, L - n, R - n);
    return T->query(1, 0, m - 1, 0, m - 1);
}

/*
int main() {
    fileio();
    int N, M, Q;
    assert(3 == scanf("%d %d %d", &N, &M, &Q));
    std::vector<int> P(N + M), A(M);
    for (int i = 0; i < N + M; ++i) {
    assert(1 == scanf("%d", &P[i]));
    }
    for (int j = 0; j < M; ++j) {
    assert(1 == scanf("%d", &A[j]));
    }
    init(N, M, P, A);

    for (int i = 0; i < Q; ++i) {
    int L, R;
    assert(2 == scanf("%d %d", &L, &R));
    printf("%d\n", count_ways(L, R));
    }
    return 0;
}*/

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