Submission #627201

#	Time	Username	Problem	Language	Result	Execution time	Memory
627201		model_code	Digital Circuit (IOI22_circuit)	C++17	16 / 100	1286 ms	4968 KiB

circuit

// 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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11