Submission #1271321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271321		model_code	Examination 2 (JOI24_examination2)	C++20	100 / 100	226 ms	58428 KiB

examination2

#include <bits/stdc++.h>

using namespace std;

template <typename T>
using vc = vector<T>;

#define all(x) x.begin(), x.end()
#define len(x) int(x.size())
#define eb emplace_back
#define fi first
#define se second
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

struct Dual_SegTree {
  int n, log, size;
  using X = array<bool, 2>;
  vc<X> dat;

  Dual_SegTree(int n) : n(n) {
    log = 1;
    while ((1 << log) < n) ++log;
    size = 1 << log;
    dat.assign(size << 1, {0, 1});
  }
  void flip(int l, int r) { apply(l, r, {1, 0}); }
  void set_true(int l, int r) { apply(l, r, {1, 1}); }
  void set_false(int l, int r) { apply(l, r, {0, 0}); }

  bool get(int p) {
    assert(0 <= p && p < n);
    p += size;
    for (int i = log; i >= 1; i--) push(p >> i);
    return dat[p][0];
  }

  void apply(int l, int r, const X a) {
    assert(0 <= l && l <= r && r <= n);
    l += size, r += size;
    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }
    while (l < r) {
      if (l & 1) apply_at(l++, a);
      if (r & 1) apply_at(--r, a);
      l >>= 1, r >>= 1;
    }
  }
  void push(int k) {
    apply_at(2 * k, dat[k]), apply_at(2 * k + 1, dat[k]);
    dat[k] = {0, 1};
  }
  void apply_at(int k, X a) { dat[k] = {a[dat[k][0]], a[dat[k][1]]}; }
};

struct Node {
  int type, l, r, size;
};

int p;
string S;
vc<Node> node;

int new_node(int t, int l, int r) {
  int k = len(node);
  int s = (t == 1 ? 1 : node[l].size + (r == -1 ? 0 : node[r].size));
  node.eb(Node{t, l, r, s});
  return k;
}

int FUNC_1();
int FUNC_2();
int FUNC_3();
int FUNC_4();
int FUNC_5();
int FUNC_6();
int IOI_FUNCTION();

int number() {
  int x = 0;
  assert('1' <= S[p] && S[p] <= '9');
  while ('0' <= S[p] && S[p] <= '9') { x = 10 * x + (S[p++] - '0'); }
  assert(1 <= x && x <= 1'000'000'000);
  return x;
}

int FUNC_1() {
  assert(S[p] == '[');
  ++p;
  int a = number();
  assert(S[p] == ']');
  ++p;
  return new_node(1, a, -1);
}

int FUNC_2() {
  if (S[p] != '(') return FUNC_1();
  assert(S[p] == '(');
  ++p;
  int k = IOI_FUNCTION();
  assert(S[p] == ')');
  ++p;
  return k;
}

int FUNC_3() {
  if (S[p] != '!') return FUNC_2();
  assert(S[p] == '!');
  ++p;
  int r = FUNC_3();
  return new_node(3, r, -1);
}

int FUNC_4() {
  int k = FUNC_3();
  while (p < len(S) && S[p] == '&') {
    ++p;
    int r = FUNC_3();
    k = new_node(4, k, r);
  }
  return k;
}

int FUNC_5() {
  int k = FUNC_4();
  while (p < len(S) && S[p] == '^') {
    ++p;
    int r = FUNC_4();
    k = new_node(5, k, r);
  }
  return k;
}

int FUNC_6() {
  int k = FUNC_5();
  while (p < len(S) && S[p] == '|') {
    ++p;
    int r = FUNC_5();
    k = new_node(6, k, r);
  }
  return k;
}

int IOI_FUNCTION() { return FUNC_6(); }

void solve() {
  int N, Q;
  cin >> N >> Q >> S;
  int root = IOI_FUNCTION();

  // make heavy child left
  for (auto& [t, l, r, s]: node) {
    if (r != -1 && node[l].size < node[r].size) swap(l, r);
  }

  vc<pair<vc<int>, vc<bool>>> ANS(len(node));

  auto dfs = [&](auto& dfs, int v) -> void {
    vc<int> path;
    vc<int> X = {0};
    int p = v;
    while (1) {
      path.eb(p);
      int r = node[p].r;
      if (r != -1) {
        dfs(dfs, r);
        X.insert(X.end(), all(ANS[r].fi));
      }
      if (node[p].type == 1) {
        X.eb(node[p].l);
        break;
      }
      p = node[p].l;
    }

    UNIQUE(X);

    int n = len(X);
    Dual_SegTree seg(n);

    while (len(path)) {
      int v = path.back();
      path.pop_back();
      auto [t, l, r, sz] = node[v];
      if (t == 1) {
        seg.set_true(LB(X, node[v].l), n);
        continue;
      }
      if (t == 3) {
        seg.flip(0, n);
        continue;
      }
      assert(t == 4 || t == 5 || t == 6);
      auto [Y, ans] = ANS[r];
      for (auto& y: Y) y = LB(X, y);
      Y.eb(n);
      for (int i = 0; i < len(Y) - 1; ++i) {
        int a = Y[i], b = Y[i + 1];
        bool k = ans[i];
        if (t == 4 && !k) seg.set_false(a, b);
        if (t == 5 && k) seg.flip(a, b);
        if (t == 6 && k) seg.set_true(a, b);
      }
    }
    vc<bool> ans(n);
    for (int i = 0; i < n; ++i) ans[i] = seg.get(i);
    ANS[v] = {X, ans};
  };

  dfs(dfs, root);

  auto [X, ans] = ANS[root];

  for (int q = 0; q < Q; ++q) {
    int x;
    cin >> x;
    int k = UB(X, x) - 1;
    cout << (ans[k] ? "True" : "False") << "\n";
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 20 / 20
• Subtask 7: 27 / 27