oj.uz

Submission #1054478

# Submission time Handle Problem Language Result Execution time Memory
1054478 2024-08-12T10:11:52 Z shmax Digital Circuit (IOI22_circuit) C++17
100 / 100
 684 ms 43088 KB 
#include "circuit.h"
#include <bits/stdc++.h>

using namespace std;
using i32 = int;
#define int long long
#define len(x) ((int)(x.size()))
template<typename T>
using vec = vector<T>;

template<typename T>
using graph = vec<vec<T>>;

vec<int> cur;
graph<int> g;
int n, m;


#define mod 1000002022

int sum(int a, int b) {
    return (a + b) - (a + b >= mod ? mod : 0);
}

int sub(int a, int b) {
    return (a - b + mod) - ((a - b + mod) >= mod ? mod : 0);
}

int mult(int a, int b) {
    return (a * b) % mod;
}

int bin_pow(int a, int b) {
    int r = 1;
    while (b) {
        if (b & 1)
            r = mult(r, a);
        a = mult(a, a);
        b >>= 1;
    }
    return r;
}


const int maxN = 1e5 + 5;


struct vertex {
    int length;
    int cur_sum;
};

vertex stree[maxN * 4];
bool pushes[maxN * 4];

void init() {
    memset(stree, 0, sizeof(stree));
    memset(pushes, 0, sizeof(pushes));
}

void push(int v, int tl, int tr) {
    if (!pushes[v]) return;
    if (tl != tr) {
        pushes[v * 2] ^= 1;
        pushes[v * 2 + 1] ^= 1;
        stree[v * 2].cur_sum = sub(stree[v * 2].length, stree[v * 2].cur_sum);
        stree[v * 2 + 1].cur_sum = sub(stree[v * 2 + 1].length, stree[v * 2 + 1].cur_sum);
    }
    pushes[v] = false;
}

void build(int v, int tl, int tr, vec<int> &length) {
    if (tl == tr) {
        stree[v].length = length[tl];
        stree[v].cur_sum = 0;
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm, length);
    build(v * 2 + 1, tm + 1, tr, length);
    stree[v].length = sum(stree[v * 2].length, stree[v * 2 + 1].length);
    stree[v].cur_sum = 0;
}


void update(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tl == l and tr == r) {
        stree[v].cur_sum = sub(stree[v].length, stree[v].cur_sum);
        pushes[v] ^= 1;
        push(v, tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    if (r <= tm) {
        update(v * 2, tl, tm, l, r);
    } else if (l > tm) {
        update(v * 2 + 1, tm + 1, tr, l, r);
    } else {
        update(v * 2, tl, tm, l, tm);
        update(v * 2 + 1, tm + 1, tr, tm + 1, r);
    }
    stree[v].cur_sum = sum(stree[v * 2].cur_sum, stree[v * 2 + 1].cur_sum);
    stree[v].length = sum(stree[v * 2].length, stree[v * 2 + 1].length);
}


int get(int v, int tl, int tr, int l, int r) {
    push(v, tl, tr);
    if (tl == l and tr == r) {
        return stree[v].cur_sum;
    }
    int tm = (tl + tr) / 2;
    if (r <= tm) {
        return get(v * 2, tl, tm, l, r);
    } else if (l > tm) {
        return get(v * 2 + 1, tm + 1, tr, l, r);
    } else {
        return sum(get(v * 2, tl, tm, l, tm), get(v * 2 + 1, tm + 1, tr, tm + 1, r));
    }
}

void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) {
    n = N;
    m = M;
    g.resize(n + m);
    for (int i = 1; i < len(P); i++) {
        g[P[i]].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        cur.push_back(A[i]);
    }
    int depth = 0;
    vec<int> d(n + m, 0);
    function<void(int)> dfs = [&](int v) {
        d[v] = depth;
        for (auto u: g[v]) {
            depth++;
            dfs(u);
            depth--;
        }
    };
    dfs(0);
    init();
    vec<int> cont(n + m, 1);
    function<void(int)> dfs1 = [&](int v) {
        cont[v] = len(g[v]);
        for (auto u: g[v]) {
            if (u < n) {
                dfs1(u);
                cont[v] = mult(cont[v], cont[u]);
            }
        }
    };
    dfs1(0);


    vec<int> dists(m);

    function<void(int, int)> fill_dist = [&](int v, int cur = 1) {
        if (v >= n) {
            dists[v - n] = cur;
            return;
        }

        vec<int> pref(len(g[v]) + 1, 1);
        for (int i = 0; i < len(g[v]); i++) {
            pref[i + 1] = mult(pref[i], cont[g[v][i]]);
        }
        vec<int> suff(len(g[v]) + 1, 1);
        for (int i = len(g[v]) - 1; i >= 0; i--) {
            suff[i] = mult(suff[i + 1], cont[g[v][i]]);
        }
        for (int i = 0; i < len(g[v]); i++) {
            int u = g[v][i];
            fill_dist(u, mult(cur, mult(pref[i], suff[i + 1])));
        }
    };
    fill_dist(0,1);

    /*
    for (int i = n; i < m + n; i++) {
        vec<bool> mark(n + m, false);
        int cur_v = i;
        while (cur_v != 0) {
            mark[cur_v] = true;
            cur_v = P[cur_v];
        }
        mark[0] = true;
        int contrib = 1;
        for (int j = 0; j < n; j++) {
            if (!mark[j]) {
                contrib = mult(contrib, len(g[j]));
            }
        }
        dists[i - n] = contrib;
    }*/
    build(1, 0, m - 1, dists);
    for (int i = 0; i < m; i++) {
        if (cur[i] == 1) {
            update(1, 0, m - 1, i, i);
        }
    }

}

i32 count_ways(i32 L, i32 R) {
    L -= n;
    R -= n;
    update(1, 0, m - 1, L, R);
    int cur_sum = get(1, 0, m - 1, 0, m - 1);
    return cur_sum;
}
//422283126

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7000 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 1 ms 7000 KB Output is correct
5 Correct 1 ms 7000 KB Output is correct
6 Correct 1 ms 7148 KB Output is correct
7 Correct 1 ms 7000 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7000 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 2 ms 7000 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 1 ms 7000 KB Output is correct
7 Correct 1 ms 7228 KB Output is correct
8 Correct 2 ms 7000 KB Output is correct
9 Correct 1 ms 7000 KB Output is correct
10 Correct 1 ms 7256 KB Output is correct
11 Correct 1 ms 7256 KB Output is correct
12 Correct 1 ms 7000 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7000 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 1 ms 7000 KB Output is correct
5 Correct 1 ms 7000 KB Output is correct
6 Correct 1 ms 7148 KB Output is correct
7 Correct 1 ms 7000 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 1 ms 7000 KB Output is correct
10 Correct 1 ms 7000 KB Output is correct
11 Correct 1 ms 7000 KB Output is correct
12 Correct 2 ms 7000 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 1 ms 7000 KB Output is correct
15 Correct 1 ms 7228 KB Output is correct
16 Correct 2 ms 7000 KB Output is correct
17 Correct 1 ms 7000 KB Output is correct
18 Correct 1 ms 7256 KB Output is correct
19 Correct 1 ms 7256 KB Output is correct
20 Correct 1 ms 7000 KB Output is correct
21 Correct 1 ms 7000 KB Output is correct
22 Correct 1 ms 7000 KB Output is correct
23 Correct 1 ms 7000 KB Output is correct
24 Correct 1 ms 7000 KB Output is correct
25 Correct 2 ms 7000 KB Output is correct
26 Correct 1 ms 7000 KB Output is correct
27 Correct 1 ms 7000 KB Output is correct
28 Correct 1 ms 7000 KB Output is correct
29 Correct 1 ms 7000 KB Output is correct
30 Correct 1 ms 7000 KB Output is correct
31 Correct 1 ms 7256 KB Output is correct
32 Correct 2 ms 7000 KB Output is correct
33 Correct 1 ms 7000 KB Output is correct
34 Correct 1 ms 7000 KB Output is correct
35 Correct 1 ms 7000 KB Output is correct
36 Correct 2 ms 7412 KB Output is correct
37 Correct 1 ms 7256 KB Output is correct
38 Correct 2 ms 7188 KB Output is correct
39 Correct 1 ms 7000 KB Output is correct
40 Correct 1 ms 7000 KB Output is correct
41 Correct 1 ms 7000 KB Output is correct
42 Correct 1 ms 7000 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 11996 KB Output is correct
2 Correct 510 ms 16856 KB Output is correct
3 Correct 599 ms 16856 KB Output is correct
4 Correct 503 ms 16856 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 11996 KB Output is correct
2 Correct 510 ms 16856 KB Output is correct
3 Correct 599 ms 16856 KB Output is correct
4 Correct 503 ms 16856 KB Output is correct
5 Correct 453 ms 12032 KB Output is correct
6 Correct 581 ms 16856 KB Output is correct
7 Correct 560 ms 16856 KB Output is correct
8 Correct 574 ms 16856 KB Output is correct
9 Correct 259 ms 7384 KB Output is correct
10 Correct 554 ms 7512 KB Output is correct
11 Correct 566 ms 7512 KB Output is correct
12 Correct 537 ms 7512 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7000 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 2 ms 7000 KB Output is correct
5 Correct 2 ms 7000 KB Output is correct
6 Correct 1 ms 7000 KB Output is correct
7 Correct 1 ms 7228 KB Output is correct
8 Correct 2 ms 7000 KB Output is correct
9 Correct 1 ms 7000 KB Output is correct
10 Correct 1 ms 7256 KB Output is correct
11 Correct 1 ms 7256 KB Output is correct
12 Correct 1 ms 7000 KB Output is correct
13 Correct 343 ms 11996 KB Output is correct
14 Correct 510 ms 16856 KB Output is correct
15 Correct 599 ms 16856 KB Output is correct
16 Correct 503 ms 16856 KB Output is correct
17 Correct 453 ms 12032 KB Output is correct
18 Correct 581 ms 16856 KB Output is correct
19 Correct 560 ms 16856 KB Output is correct
20 Correct 574 ms 16856 KB Output is correct
21 Correct 259 ms 7384 KB Output is correct
22 Correct 554 ms 7512 KB Output is correct
23 Correct 566 ms 7512 KB Output is correct
24 Correct 537 ms 7512 KB Output is correct
25 Correct 610 ms 21824 KB Output is correct
26 Correct 619 ms 21964 KB Output is correct
27 Correct 593 ms 22080 KB Output is correct
28 Correct 540 ms 21964 KB Output is correct
29 Correct 595 ms 40652 KB Output is correct
30 Correct 606 ms 40652 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7000 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 1 ms 7000 KB Output is correct
5 Correct 1 ms 7000 KB Output is correct
6 Correct 1 ms 7148 KB Output is correct
7 Correct 1 ms 7000 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 1 ms 7000 KB Output is correct
10 Correct 1 ms 7000 KB Output is correct
11 Correct 1 ms 7000 KB Output is correct
12 Correct 2 ms 7000 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 1 ms 7000 KB Output is correct
15 Correct 1 ms 7228 KB Output is correct
16 Correct 2 ms 7000 KB Output is correct
17 Correct 1 ms 7000 KB Output is correct
18 Correct 1 ms 7256 KB Output is correct
19 Correct 1 ms 7256 KB Output is correct
20 Correct 1 ms 7000 KB Output is correct
21 Correct 1 ms 7000 KB Output is correct
22 Correct 1 ms 7000 KB Output is correct
23 Correct 1 ms 7000 KB Output is correct
24 Correct 1 ms 7000 KB Output is correct
25 Correct 2 ms 7000 KB Output is correct
26 Correct 1 ms 7000 KB Output is correct
27 Correct 1 ms 7000 KB Output is correct
28 Correct 1 ms 7000 KB Output is correct
29 Correct 1 ms 7000 KB Output is correct
30 Correct 1 ms 7000 KB Output is correct
31 Correct 1 ms 7256 KB Output is correct
32 Correct 2 ms 7000 KB Output is correct
33 Correct 1 ms 7000 KB Output is correct
34 Correct 1 ms 7000 KB Output is correct
35 Correct 1 ms 7000 KB Output is correct
36 Correct 2 ms 7412 KB Output is correct
37 Correct 1 ms 7256 KB Output is correct
38 Correct 2 ms 7188 KB Output is correct
39 Correct 1 ms 7000 KB Output is correct
40 Correct 1 ms 7000 KB Output is correct
41 Correct 1 ms 7000 KB Output is correct
42 Correct 1 ms 7000 KB Output is correct
43 Correct 415 ms 7512 KB Output is correct
44 Correct 512 ms 7512 KB Output is correct
45 Correct 537 ms 7512 KB Output is correct
46 Correct 500 ms 7768 KB Output is correct
47 Correct 572 ms 7768 KB Output is correct
48 Correct 508 ms 7768 KB Output is correct
49 Correct 525 ms 7768 KB Output is correct
50 Correct 508 ms 7768 KB Output is correct
51 Correct 569 ms 7540 KB Output is correct
52 Correct 485 ms 7536 KB Output is correct
53 Correct 496 ms 8280 KB Output is correct
54 Correct 565 ms 7768 KB Output is correct
55 Correct 530 ms 7512 KB Output is correct
56 Correct 498 ms 7512 KB Output is correct
57 Correct 550 ms 7512 KB Output is correct
58 Correct 588 ms 8536 KB Output is correct
59 Correct 526 ms 8788 KB Output is correct
60 Correct 482 ms 8792 KB Output is correct
61 Correct 561 ms 7768 KB Output is correct
62 Correct 521 ms 7512 KB Output is correct
63 Correct 542 ms 7512 KB Output is correct
64 Correct 586 ms 7508 KB Output is correct
65 Correct 247 ms 7380 KB Output is correct
66 Correct 564 ms 7512 KB Output is correct
67 Correct 497 ms 7512 KB Output is correct
68 Correct 414 ms 7512 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 7000 KB Output is correct
2 Correct 1 ms 7000 KB Output is correct
3 Correct 1 ms 7000 KB Output is correct
4 Correct 1 ms 7000 KB Output is correct
5 Correct 1 ms 7000 KB Output is correct
6 Correct 1 ms 7148 KB Output is correct
7 Correct 1 ms 7000 KB Output is correct
8 Correct 1 ms 7000 KB Output is correct
9 Correct 1 ms 7000 KB Output is correct
10 Correct 1 ms 7000 KB Output is correct
11 Correct 1 ms 7000 KB Output is correct
12 Correct 2 ms 7000 KB Output is correct
13 Correct 2 ms 7000 KB Output is correct
14 Correct 1 ms 7000 KB Output is correct
15 Correct 1 ms 7228 KB Output is correct
16 Correct 2 ms 7000 KB Output is correct
17 Correct 1 ms 7000 KB Output is correct
18 Correct 1 ms 7256 KB Output is correct
19 Correct 1 ms 7256 KB Output is correct
20 Correct 1 ms 7000 KB Output is correct
21 Correct 1 ms 7000 KB Output is correct
22 Correct 1 ms 7000 KB Output is correct
23 Correct 1 ms 7000 KB Output is correct
24 Correct 1 ms 7000 KB Output is correct
25 Correct 2 ms 7000 KB Output is correct
26 Correct 1 ms 7000 KB Output is correct
27 Correct 1 ms 7000 KB Output is correct
28 Correct 1 ms 7000 KB Output is correct
29 Correct 1 ms 7000 KB Output is correct
30 Correct 1 ms 7000 KB Output is correct
31 Correct 1 ms 7256 KB Output is correct
32 Correct 2 ms 7000 KB Output is correct
33 Correct 1 ms 7000 KB Output is correct
34 Correct 1 ms 7000 KB Output is correct
35 Correct 1 ms 7000 KB Output is correct
36 Correct 2 ms 7412 KB Output is correct
37 Correct 1 ms 7256 KB Output is correct
38 Correct 2 ms 7188 KB Output is correct
39 Correct 1 ms 7000 KB Output is correct
40 Correct 1 ms 7000 KB Output is correct
41 Correct 1 ms 7000 KB Output is correct
42 Correct 1 ms 7000 KB Output is correct
43 Correct 343 ms 11996 KB Output is correct
44 Correct 510 ms 16856 KB Output is correct
45 Correct 599 ms 16856 KB Output is correct
46 Correct 503 ms 16856 KB Output is correct
47 Correct 453 ms 12032 KB Output is correct
48 Correct 581 ms 16856 KB Output is correct
49 Correct 560 ms 16856 KB Output is correct
50 Correct 574 ms 16856 KB Output is correct
51 Correct 259 ms 7384 KB Output is correct
52 Correct 554 ms 7512 KB Output is correct
53 Correct 566 ms 7512 KB Output is correct
54 Correct 537 ms 7512 KB Output is correct
55 Correct 610 ms 21824 KB Output is correct
56 Correct 619 ms 21964 KB Output is correct
57 Correct 593 ms 22080 KB Output is correct
58 Correct 540 ms 21964 KB Output is correct
59 Correct 595 ms 40652 KB Output is correct
60 Correct 606 ms 40652 KB Output is correct
61 Correct 415 ms 7512 KB Output is correct
62 Correct 512 ms 7512 KB Output is correct
63 Correct 537 ms 7512 KB Output is correct
64 Correct 500 ms 7768 KB Output is correct
65 Correct 572 ms 7768 KB Output is correct
66 Correct 508 ms 7768 KB Output is correct
67 Correct 525 ms 7768 KB Output is correct
68 Correct 508 ms 7768 KB Output is correct
69 Correct 569 ms 7540 KB Output is correct
70 Correct 485 ms 7536 KB Output is correct
71 Correct 496 ms 8280 KB Output is correct
72 Correct 565 ms 7768 KB Output is correct
73 Correct 530 ms 7512 KB Output is correct
74 Correct 498 ms 7512 KB Output is correct
75 Correct 550 ms 7512 KB Output is correct
76 Correct 588 ms 8536 KB Output is correct
77 Correct 526 ms 8788 KB Output is correct
78 Correct 482 ms 8792 KB Output is correct
79 Correct 561 ms 7768 KB Output is correct
80 Correct 521 ms 7512 KB Output is correct
81 Correct 542 ms 7512 KB Output is correct
82 Correct 586 ms 7508 KB Output is correct
83 Correct 247 ms 7380 KB Output is correct
84 Correct 564 ms 7512 KB Output is correct
85 Correct 497 ms 7512 KB Output is correct
86 Correct 414 ms 7512 KB Output is correct
87 Correct 1 ms 7000 KB Output is correct
88 Correct 356 ms 20592 KB Output is correct
89 Correct 560 ms 16588 KB Output is correct
90 Correct 533 ms 16860 KB Output is correct
91 Correct 527 ms 22476 KB Output is correct
92 Correct 507 ms 22588 KB Output is correct
93 Correct 553 ms 22708 KB Output is correct
94 Correct 557 ms 22704 KB Output is correct
95 Correct 551 ms 22548 KB Output is correct
96 Correct 565 ms 16584 KB Output is correct
97 Correct 480 ms 16452 KB Output is correct
98 Correct 456 ms 33616 KB Output is correct
99 Correct 587 ms 21904 KB Output is correct
100 Correct 516 ms 19064 KB Output is correct
101 Correct 562 ms 17356 KB Output is correct
102 Correct 684 ms 15052 KB Output is correct
103 Correct 632 ms 40732 KB Output is correct
104 Correct 629 ms 43088 KB Output is correct
105 Correct 609 ms 43088 KB Output is correct
106 Correct 580 ms 20432 KB Output is correct
107 Correct 595 ms 15436 KB Output is correct
108 Correct 609 ms 15820 KB Output is correct
109 Correct 654 ms 15316 KB Output is correct