oj.uz

Submission #627202

# Submission time Handle Problem Language Result Execution time Memory
627202 2022-08-12T11:20:10 Z model_code Digital Circuit (IOI22_circuit) C++17
52 / 100
 1465 ms 7328 KB 
// failed/solution-prabowo-binary.cpp
// O(N + M + Q log M)

#include "circuit.h"

#include <algorithm>
#include <utility>
#include <vector>

const int kMod = 1000002022;

int N;

struct SegTree {
 private:
  int n;
  struct Node {
    int val[2];
    bool lazy;
    Node(int v0=0, int v1=0) {
      val[0] = v0;
      val[1] = v1;
      lazy = false;
    }

    Node operator + (const Node &other) {
      return Node((val[0] + other.val[0]) % kMod,
                  (val[1] + other.val[1]) % kMod);
    }
  };
  std::vector<Node> nodes;

  inline void toggle(int idx) {
    std::swap(nodes[idx].val[0], nodes[idx].val[1]);
    nodes[idx].lazy = !nodes[idx].lazy;
  }

  inline void pull(int idx, int l, int r) {
    int mid = (l + r) >> 1;
    nodes[idx] = nodes[idx + 1] + nodes[idx + (mid - l) * 2];
  }

  inline void push(int idx, int l, int r) {
    if (!nodes[idx].lazy) return;
    int mid = (l + r) >> 1;
    toggle(idx + 1);
    toggle(idx + (mid - l) * 2);
    nodes[idx].lazy = false;
  }

  void build(int idx, int l, int r, const std::vector<std::pair<int, int>> &v) {
    if (l + 1 == r) {
      nodes[idx] = Node(v[l].first, v[l].second);
      return;
    }
    int mid = (l + r) >> 1;
    build(idx + 1, l, mid, v);
    build(idx + (mid - l) * 2, mid, r, v);
    pull(idx, l, r);
  }

  void update(int idx, int l, int r, int ll, int rr) {
    if (l >= rr || r <= ll) {
      return;
    }
    if (l >= ll && r <= rr) {
      return toggle(idx);
    }
    push(idx, l, r);
    int mid = (l + r) >> 1;
    update(idx + 1, l, mid, ll, rr);
    update(idx + (mid - l) * 2, mid, r, ll, rr);
    pull(idx, l, r);
  }

 public:
  void init(const std::vector<std::pair<int, int>> &v) {
    n = static_cast<int>(v.size());
    nodes.resize(2 * n - 1);
    build(0, 0, n, v);
  }

  void update(int l, int r) {
    update(0, 0, n, l, r);
  }

  int query() {
    return nodes[0].val[1];
  }
} segtree;

void init(int _N, int M, std::vector<int> P, std::vector<int> A) {
  N = _N;
  std::vector<int> depth(N + M);
  for (int i = 1; i < N + M; ++i) {
    depth[i] = depth[P[i]] + 1;
  }

  std::vector<int> twos(N);
  twos[0] = 1;
  for (int i = 1; i < N; ++i) {
    twos[i] = 2 * twos[i - 1] % kMod;
  }

  std::vector<int> contribution(M);
  for (int j = 0; j < M; ++j) {
    contribution[j] = twos[N - depth[j + N]];
  }

  std::vector<std::pair<int, int>> v(M);
  for (int i = 0; i < M; ++i) {
    if (A[i]) {
      v[i].second = contribution[i];
    } else {
      v[i].first = contribution[i];
    }
  }
  segtree.init(v);
}

int count_ways(int L, int R) {
  segtree.update(L - N, R - N + 1);
  return segtree.query();
}

Subtask #1
2.0 / 2.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 288 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 2640 KB Output is correct
2 Correct 892 ms 4908 KB Output is correct
3 Correct 783 ms 4892 KB Output is correct
4 Correct 1079 ms 4852 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 2640 KB Output is correct
2 Correct 892 ms 4908 KB Output is correct
3 Correct 783 ms 4892 KB Output is correct
4 Correct 1079 ms 4852 KB Output is correct
5 Correct 701 ms 2600 KB Output is correct
6 Correct 990 ms 4920 KB Output is correct
7 Correct 933 ms 4896 KB Output is correct
8 Correct 772 ms 4896 KB Output is correct
9 Correct 514 ms 408 KB Output is correct
10 Correct 1130 ms 572 KB Output is correct
11 Correct 1120 ms 556 KB Output is correct
12 Correct 1098 ms 548 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 538 ms 2640 KB Output is correct
14 Correct 892 ms 4908 KB Output is correct
15 Correct 783 ms 4892 KB Output is correct
16 Correct 1079 ms 4852 KB Output is correct
17 Correct 701 ms 2600 KB Output is correct
18 Correct 990 ms 4920 KB Output is correct
19 Correct 933 ms 4896 KB Output is correct
20 Correct 772 ms 4896 KB Output is correct
21 Correct 514 ms 408 KB Output is correct
22 Correct 1130 ms 572 KB Output is correct
23 Correct 1120 ms 556 KB Output is correct
24 Correct 1098 ms 548 KB Output is correct
25 Correct 1133 ms 7188 KB Output is correct
26 Correct 978 ms 7316 KB Output is correct
27 Correct 1152 ms 7236 KB Output is correct
28 Correct 901 ms 7208 KB Output is correct
29 Correct 1043 ms 7328 KB Output is correct
30 Correct 1465 ms 7312 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 288 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 288 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -