oj.uz

Submission #627201

# Submission time Handle Problem Language Result Execution time Memory
627201 2022-08-12T11:20:05 Z model_code Digital Circuit (IOI22_circuit) C++17
16 / 100
 1286 ms 4968 KB 
// failed/solution-hocky-segtree.cpp
#include "circuit.h"

#include <bits/stdc++.h>
using namespace std;

const int kMod = (int) 1e9 + 2022;

struct Node {
  int left_bound, right_bound;
  int memo[2] = {0, 0};
};

struct Tree {
  int n;
  vector<Node> segment_tree;
  vector<int> lazy;
  vector<int> is_on;

  Tree(int m_init, vector<int> on_init) :
    n(m_init),
    segment_tree(2 * n - 1),
    lazy (2 * n - 1),
    is_on(on_init) {
    get_bounds(0);
    build(0);
  }

  bool is_leaf(int pos) {
    return (pos >= n - 1);
  }

  void get_bounds(int pos) {
    assert(pos < 2 * n - 1);
    if (is_leaf(pos)) {
      assert(pos - (n - 1) <= n);
      segment_tree[pos].left_bound = segment_tree[pos].right_bound = pos - (n - 1);
      return;
    }

    get_bounds(pos * 2 + 1);
    get_bounds(pos * 2 + 2);

    segment_tree[pos].left_bound = min(segment_tree[pos * 2 + 1].left_bound, segment_tree[pos * 2 + 2].left_bound);
    segment_tree[pos].right_bound = max(segment_tree[pos * 2 + 1].right_bound, segment_tree[pos * 2 + 2].right_bound);

    if(segment_tree[pos].left_bound > segment_tree[pos].right_bound)
      swap(segment_tree[pos].left_bound, segment_tree[pos].right_bound);
    
    assert(segment_tree[pos].left_bound < segment_tree[pos].right_bound);
  }

  void fix_segment_tree(int index) {

    // Fix segment tree
    vector<int> knapsack(3);
    knapsack[0] = 1LL * get_result(index * 2 + 1, 0) * get_result(index * 2 + 2, 0) % kMod;
    knapsack[1] = 1LL * get_result(index * 2 + 1, 1) * get_result(index * 2 + 2, 0) % kMod +
                  1LL * get_result(index * 2 + 1, 0) * get_result(index * 2 + 2, 1) % kMod;
    knapsack[1] %= kMod;
    knapsack[2] = 1LL * get_result(index * 2 + 1, 1) * get_result(index * 2 + 2, 1) % kMod;

    segment_tree[index].memo[0] = segment_tree[index].memo[1] = knapsack[1];
    segment_tree[index].memo[0] = (segment_tree[index].memo[0] + knapsack[0] * 2 % kMod) % kMod;
    segment_tree[index].memo[1] = (segment_tree[index].memo[1] + knapsack[2] * 2 % kMod) % kMod;

  }

  void build(int index) {
    int left_bound = segment_tree[index].left_bound;
    int right_bound = segment_tree[index].right_bound;
    if (is_leaf(index)) {
      segment_tree[index].memo[is_on[left_bound]] = 1;
      assert(left_bound == right_bound);
      return;
    }
    build(index * 2 + 1);
    build(index * 2 + 2);
    fix_segment_tree(index);
  }

  int get_result(int index, bool intend) {
    return segment_tree[index].memo[intend];
  }

  void lazy_propagate(int index) {
    if (lazy[index] == 0) return;
    lazy[index] = 0;
    swap(segment_tree[index].memo[0], segment_tree[index].memo[1]);
    if (!is_leaf(index)) {
      lazy[index * 2 + 1] ^= 1;
      lazy[index * 2 + 2] ^= 1;
    }
  }

  int toggle(int left_target, int right_target) {
    toggle(0, left_target - (n - 1), right_target - (n - 1));
    return get_result(0, 1);
  }

  void toggle(int index,
              int left_target, int right_target) {
    lazy_propagate(index);
    int left_bound = segment_tree[index].left_bound;
    int right_bound = segment_tree[index].right_bound;
    if (left_target > right_bound || right_target < left_bound) return;
    if (left_target <= left_bound && right_bound <= right_target) {
      // Toggle this tree, enable lazy;
      lazy[index] ^= 1;
      lazy_propagate(index);
      return;
    }
    toggle(index * 2 + 1, left_target, right_target);
    toggle(index * 2 + 2, left_target, right_target);
    fix_segment_tree(index);
    return;
  }
};

Tree *solution;

void init(int N, int M, vector<int>, vector<int> A) {
  assert(N == M - 1);
  solution = new Tree(M, A);
}

int count_ways(int L, int R) {
  return solution->toggle(L, R);
}

Subtask #1
0 / 2.0

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

Subtask #2
0 / 7.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 256 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '573051996'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Runtime error 1 ms 336 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 940 ms 2620 KB Output is correct
2 Correct 1151 ms 4964 KB Output is correct
3 Correct 1125 ms 4968 KB Output is correct
4 Correct 1121 ms 4920 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 2620 KB Output is correct
2 Correct 1151 ms 4964 KB Output is correct
3 Correct 1125 ms 4968 KB Output is correct
4 Correct 1121 ms 4920 KB Output is correct
5 Correct 1048 ms 2664 KB Output is correct
6 Correct 1245 ms 4908 KB Output is correct
7 Correct 1286 ms 4896 KB Output is correct
8 Correct 916 ms 4892 KB Output is correct
9 Correct 636 ms 336 KB Output is correct
10 Correct 1161 ms 600 KB Output is correct
11 Correct 1127 ms 640 KB Output is correct
12 Correct 1039 ms 592 KB Output is correct

Subtask #6
0 / 27.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 256 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '706880838', found: '573051996'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Runtime error 1 ms 336 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 1 ms 208 KB Output is correct
2 Runtime error 1 ms 336 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -