Submission #1058832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058832		dozer	Digital Circuit (IOI22_circuit)	C++17	100 / 100	697 ms	64468 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 500005

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];
vector<int> pre[MAXN], suf[MAXN];
int val[MAXN], sz[MAXN], n, m;

void dfs(int node){
    sz[node] = max((int)1, (int)adj[node].size());
    pre[node].resize(adj[node].size());
    suf[node].resize(adj[node].size());
    for (auto i : adj[node]){
        dfs(i);
        sz[node] = mul(sz[node], sz[i]);
    }

    if (adj[node].empty()) return;
    pre[node][0] = sz[adj[node][0]];
    suf[node][(int)adj[node].size() - 1] = sz[adj[node].back()];

    for (int i = 1; i < adj[node].size(); i++)
        pre[node][i] = mul(pre[node][i - 1], sz[adj[node][i]]);

    for (int i = (int)adj[node].size() - 2; i >= 0; i--)
        suf[node][i] = mul(suf[node][i + 1], sz[adj[node][i]]);

}


void dfs2(int node, int x){
    val[node] = x;
    if (adj[node].empty()) return;
    for (int i = 0; i < adj[node].size(); i++){
        int m = 1;
        if (i > 0) m = mul(m, pre[node][i - 1]);
        if (i + 1 < adj[node].size()) m = mul(m, suf[node][i + 1]);
        dfs2(adj[node][i], mul(x, m));
    }
}


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;
}
*/

Compilation message (stderr)

circuit.cpp: In function 'void dfs(int)':
circuit.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i = 1; i < adj[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~
circuit.cpp: In function 'void dfs2(int, int)':
circuit.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |     for (int i = 0; i < adj[node].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~
circuit.cpp:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |         if (i + 1 < adj[node].size()) m = mul(m, suf[node][i + 1]);
      |             ~~~~~~^~~~~~~~~~~~~~~~~~

• 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