oj.uz

Submission #825788

# Submission time Handle Problem Language Result Execution time Memory
825788 2023-08-15T08:05:31 Z becaido Digital Circuit (IOI22_circuit) C++17
50 / 100
 967 ms 19244 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "circuit.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int MOD = 1000002022;
const int SIZE = 2e5 + 5;

int n, m, ans;
vector<int> adj[SIZE];
int a[SIZE], coef[SIZE], all[SIZE], pre[SIZE];

int add(const int &x, const int &y) {
    return x + y >= MOD ? x + y - MOD : x < -y ? x + y + MOD : x + y;
}
int mul(const int &x, const int &y) {
    return 1ll * x * y % MOD;
}

struct Node {
    int sum = 0, lazy = 0;
} node[SIZE * 4];

void build(int pos, int l, int r) {
    if (l == r) {
        if (a[l]) node[pos].sum = coef[l];
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    node[pos].sum = add(node[lpos].sum, node[rpos].sum);
}
void push(int pos, int l, int r) {
    if (!node[pos].lazy) return;
    node[pos].sum = add(pre[r], -add((l ? pre[l - 1] : 0), node[pos].sum));
    if (l < r) {
        node[lpos].lazy ^= 1;
        node[rpos].lazy ^= 1;
    }
    node[pos].lazy = 0;
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    node[pos].sum = add(node[lpos].sum, node[rpos].sum);
}
void upd(int pos, int l, int r, int L, int R) {
    if (l == L && r == R) {
        node[pos].lazy ^= 1;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid);
    else if (l > mid) upd(rpos, l, r, mid + 1, R);
    else {
        upd(lpos, l, mid, L, mid);
        upd(rpos, mid + 1, r, mid + 1, R);
    }
    pull(pos, L, R);
}

void dfs0(int pos) {
    int pro = 1;
    for (int np : adj[pos]) {
        dfs0(np);
        pro = mul(pro, all[np]);
    }
    if (adj[pos].size()) pro = mul(pro, adj[pos].size());
    all[pos] = pro;
}
void dfs(int pos, int cur) {
    if (adj[pos].size() == 0) {
        coef[pos - n] = cur;
        return;
    }
    assert(adj[pos].size() == 2);
    dfs(adj[pos][0], mul(cur, all[adj[pos][1]]));
    dfs(adj[pos][1], mul(cur, all[adj[pos][0]]));
}

void init(int N, int M, vector<int> P, vector<int> A) {
    n = N, m = M;
    FOR (i, 1, n + m - 1) adj[P[i]].pb(i);
    dfs0(0);
    dfs(0, 1);
    FOR (i, 0, m - 1) {
        a[i] = A[i];
        pre[i] = add((i ? pre[i - 1] : 0), coef[i]);
    }
    build(1, 0, m - 1);
}

int count_ways(int L, int R) {
    L -= n, R -= n;
    upd(1, L, R, 0, m - 1);
    push(1, 0, m - 1);
    return node[1].sum;
}

/*
in1
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
out1
2
0
6
*/

#ifdef WAIMAI
int main() {
  int N, M, Q;
  assert(3 == scanf("%d %d %d", &N, &M, &Q));
  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;
}
#endif

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 7 ms 9936 KB Execution killed with signal 6
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 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 7 ms 9936 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 7928 KB Output is correct
2 Correct 623 ms 10824 KB Output is correct
3 Correct 573 ms 10864 KB Output is correct
4 Correct 681 ms 10312 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 7928 KB Output is correct
2 Correct 623 ms 10824 KB Output is correct
3 Correct 573 ms 10864 KB Output is correct
4 Correct 681 ms 10312 KB Output is correct
5 Correct 494 ms 7880 KB Output is correct
6 Correct 686 ms 10900 KB Output is correct
7 Correct 706 ms 10880 KB Output is correct
8 Correct 663 ms 10900 KB Output is correct
9 Correct 287 ms 5200 KB Output is correct
10 Correct 548 ms 5328 KB Output is correct
11 Correct 665 ms 5328 KB Output is correct
12 Correct 629 ms 5328 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 3 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 5072 KB Output is correct
7 Correct 3 ms 5072 KB Output is correct
8 Correct 3 ms 5072 KB Output is correct
9 Correct 3 ms 5072 KB Output is correct
10 Correct 3 ms 5072 KB Output is correct
11 Correct 3 ms 5072 KB Output is correct
12 Correct 3 ms 5072 KB Output is correct
13 Correct 386 ms 7928 KB Output is correct
14 Correct 623 ms 10824 KB Output is correct
15 Correct 573 ms 10864 KB Output is correct
16 Correct 681 ms 10312 KB Output is correct
17 Correct 494 ms 7880 KB Output is correct
18 Correct 686 ms 10900 KB Output is correct
19 Correct 706 ms 10880 KB Output is correct
20 Correct 663 ms 10900 KB Output is correct
21 Correct 287 ms 5200 KB Output is correct
22 Correct 548 ms 5328 KB Output is correct
23 Correct 665 ms 5328 KB Output is correct
24 Correct 629 ms 5328 KB Output is correct
25 Correct 749 ms 14332 KB Output is correct
26 Correct 729 ms 14396 KB Output is correct
27 Correct 821 ms 14408 KB Output is correct
28 Correct 524 ms 14488 KB Output is correct
29 Correct 770 ms 19244 KB Output is correct
30 Correct 967 ms 19092 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 7 ms 9936 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Runtime error 7 ms 9936 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -