oj.uz

Submission #826201

# Submission time Handle Problem Language Result Execution time Memory
826201 2023-08-15T11:10:18 Z PixelCat Digital Circuit (IOI22_circuit) C++17
50 / 100
 3000 ms 27552 KB 
#include "circuit.h"

#ifdef NYAOWO
#include "stub.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
const int MOD = 1'000'002'022;

#define L(id) ((id) * 2 + 1)
#define R(id) ((id) * 2 + 2)
struct SegTree {
    struct Node {
        bool flip;
        int dp1, sum;
    } a[MAXN * 4 + 10];
    void build(int id, int l, int r, int* A) {
        a[id].flip = 0;
        if(l == r) {
            a[id].sum = A[l];
            a[id].dp1 = 0;
            return;
        }
        int m = (l + r) / 2;
        build(L(id), l, m, A);
        build(R(id), m + 1, r, A);
        a[id].dp1 = (a[L(id)].dp1 + a[R(id)].dp1) % MOD;
        a[id].sum = (a[L(id)].sum + a[R(id)].sum) % MOD;
    }
    void range_flip(int id, int l, int r, int L, int R) {
        if(l >= L && r <= R) {
            a[id].flip ^= 1;
            a[id].dp1 = (a[id].sum - a[id].dp1) % MOD;
            return;
        }
        int m = (l + r) / 2;
        if(L <= m) range_flip(L(id), l, m, L, R);
        if(R > m)  range_flip(R(id), m + 1, r, L, R);
        a[id].dp1 = (a[L(id)].dp1 + a[R(id)].dp1) % MOD;
        if(a[id].flip) a[id].dp1 = (a[id].sum - a[id].dp1) % MOD;
    }
    int qry() {
        return (a[0].dp1 + MOD) % MOD;
    }
} seg;

int n, m;
vector<int> adj[MAXN + 10];
int p[MAXN + 10];
int a[MAXN + 10];

int s[MAXN + 10];

void dfs(int x) {
    if(x >= n) {
        s[x] = 1;
        return;
    }
    s[x] = sz(adj[x]);
    for(auto &i:adj[x]) {
        dfs(i);
        s[x] = s[x] * s[i] % MOD;
    }
}

int ss[MAXN + 10];
void dfs2(int x, int owo) {
    if(x >= n) {
        ss[x] = owo;
        return;
    }
    int l = adj[x][0];
    int r = adj[x][1];
    dfs2(l, owo * s[r] % MOD);
    dfs2(r, owo * s[l] % MOD);
}

// int ans = 0;
// void update_leaf(int pos, int val) {
//     ans = ((ans + val * ss[pos]) % MOD + MOD) % MOD;
// }

void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) {
    n = N; m = M;
    p[0] = -1;
    For(i, 1, n + m - 1) {
        adj[P[i]].eb(i);
        p[i] = P[i];
    }
    dfs(0);
    dfs2(0, 1);
    seg.build(0, n, n + m - 1, ss);
    For(i, 0, m - 1) {
        a[n + i] = A[i];
        if(A[i]) seg.range_flip(0, n, n + m - 1, n + i, n + i);
        // update_leaf(n + i, A[i]);
    }
}

i32 count_ways(i32 L, i32 R) {
    seg.range_flip(0, n, n + m - 1, L, R);
    return (i32) seg.qry();
    // int i = min(L, R);
    // int last = i;
    // int d = 1 - 2 * a[i];
    // a[i] += d;
    // update_leaf(i, d);
    // return (i32)ans;
}

/*

3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6

2
0
6

*/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Execution timed out 3082 ms 4944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5100 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 2 ms 5200 KB Output is correct
11 Correct 3 ms 5200 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Execution timed out 3082 ms 4944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 9892 KB Output is correct
2 Correct 642 ms 14752 KB Output is correct
3 Correct 625 ms 14720 KB Output is correct
4 Correct 614 ms 14736 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 9892 KB Output is correct
2 Correct 642 ms 14752 KB Output is correct
3 Correct 625 ms 14720 KB Output is correct
4 Correct 614 ms 14736 KB Output is correct
5 Correct 559 ms 9796 KB Output is correct
6 Correct 698 ms 14732 KB Output is correct
7 Correct 658 ms 14664 KB Output is correct
8 Correct 656 ms 14724 KB Output is correct
9 Correct 337 ms 5328 KB Output is correct
10 Correct 654 ms 5584 KB Output is correct
11 Correct 689 ms 5584 KB Output is correct
12 Correct 529 ms 5584 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4944 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 2 ms 5072 KB Output is correct
5 Correct 2 ms 5072 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5100 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 2 ms 5200 KB Output is correct
11 Correct 3 ms 5200 KB Output is correct
12 Correct 2 ms 5072 KB Output is correct
13 Correct 343 ms 9892 KB Output is correct
14 Correct 642 ms 14752 KB Output is correct
15 Correct 625 ms 14720 KB Output is correct
16 Correct 614 ms 14736 KB Output is correct
17 Correct 559 ms 9796 KB Output is correct
18 Correct 698 ms 14732 KB Output is correct
19 Correct 658 ms 14664 KB Output is correct
20 Correct 656 ms 14724 KB Output is correct
21 Correct 337 ms 5328 KB Output is correct
22 Correct 654 ms 5584 KB Output is correct
23 Correct 689 ms 5584 KB Output is correct
24 Correct 529 ms 5584 KB Output is correct
25 Correct 606 ms 21064 KB Output is correct
26 Correct 693 ms 21296 KB Output is correct
27 Correct 746 ms 21336 KB Output is correct
28 Correct 516 ms 21244 KB Output is correct
29 Correct 706 ms 27528 KB Output is correct
30 Correct 620 ms 27552 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Execution timed out 3082 ms 4944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Execution timed out 3082 ms 4944 KB Time limit exceeded
3 Halted 0 ms 0 KB -