Submission #668690

#	Time	Username	Problem	Language	Result	Execution time	Memory
668690		hoanghq2004	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1092 ms	33056 KiB

circuit

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "circuit.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 6e5 + 10;
const int mod = 1e9 + 2022;

int n, m;
vector <int> g[N];
int sz[N];

void dfs(int u) {
    sz[u] = (u >= n ? 1 : g[u].size());
    for (auto v: g[u]) {
        dfs(v);
        sz[u] = 1LL * sz[u] * sz[v] % mod;
    }
}

int c[N], prf[N], suf[N];
int mul[N];

void fix(int u) {
    int num = 0;
    for (auto v: g[u]) c[++num] = v;
    prf[0] = suf[num + 1] = 1;
    for (int i = 1; i <= num; ++i) prf[i] = 1LL * prf[i - 1] * sz[c[i]] % mod;
    for (int i = num; i >= 1; --i) suf[i] = 1LL * suf[i + 1] * sz[c[i]] % mod;
    for (int i = 1; i <= num; ++i)
        mul[c[i]] = 1LL * prf[i - 1] * suf[i + 1] % mod;
    for (auto v: g[u]) fix(v);
}

int ans = 0;

void add(int& a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int st[N * 4];
int lz[N * 4];

void build(int id, int L, int R) {
    if (R - L == 1) {
        st[id] = mul[L + n];
        return;
    }
    int mid = L + R >> 1;
    build(id * 2, L, mid);
    build(id * 2 + 1, mid, R);
    st[id] = (st[id * 2] + st[id * 2 + 1]) % mod;
}

void push(int id, int val) {
    if (!val) return;
    st[id] = (mod - st[id]) % mod;
    lz[id] ^= 1;
}

void update(int id, int L, int R, int u, int v) {
    if (u >= R || L >= v) return;
    if (u <= L && R <= v) {
        push(id, 1);
        return;
    }
    push(id * 2, lz[id]);
    push(id * 2 + 1, lz[id]);
    lz[id] = 0;
    int mid = L + R >> 1;
    update(id * 2, L, mid, u, v);
    update(id * 2 + 1, mid, R, u, v);
    st[id] = (st[id * 2] + st[id * 2 + 1]) % mod;
}

int get(int id, int L, int R, int u, int v) {
    if (u >= R || L >= v) return 0;
    if (u <= L && R <= v) return st[id];
    push(id * 2, lz[id]);
    push(id * 2 + 1, lz[id]);
    lz[id] = 0;
    int mid = L + R >> 1;
    return (get(id * 2, L, mid, u, v) + get(id * 2 + 1, mid, R, u, v)) % mod;
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M;
    for (int i = 1; i < n + m; ++i) g[P[i]].push_back(i);
    mul[0] = 1;
    dfs(0);
    fix(0);
    for (int i = 1; i < n + m; ++i) mul[i] = 1LL * mul[i] * mul[P[i]] % mod;
    build(1, 0, m);
    for (int i = 0; i < m; ++i) if (A[i]) add(ans, get(1, 0, m, i, i + 1)), update(1, 0, m, i, i + 1);
}


int count_ways(int L, int R) {
    ++R;
    add(ans, get(1, 0, m, L - n, R - n));
    update(1, 0, m, L - n, R - n);
    return ans;
}

//
//int main() {
//  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 build(int, int, int)':
circuit.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = L + R >> 1;
      |               ~~^~~
circuit.cpp: In function 'void update(int, int, int, int, int)':
circuit.cpp:80:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid = L + R >> 1;
      |               ~~^~~
circuit.cpp: In function 'int get(int, int, int, int, int)':
circuit.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     int mid = L + R >> 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