Submission #627950

#	Time	Username	Problem	Language	Result	Execution time	Memory
627950		lunchbox	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1244 ms	29384 KiB

circuit

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

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int MD = 1000002022;

template<int N>
struct Lst {
  static const int N_ = 1 << (__lg(N - 1) + 1);
  int n, z[N_];
  pi t[N_ * 2];

  void bld(int k, int l, int r, const vector<pi>& ar) {
    if (l == r)
      t[k] = ar[l];
    else {
      int m = (l + r) / 2;
      z[k] = 0;
      bld(k << 1 | 0, l, m, ar), bld(k << 1 | 1, m + 1, r, ar);
      pul(k, l, r);
    }
  }
  void bld(int n_, const vector<pi>& ar) {
    n = n_;
    bld(1, 0, n - 1, ar);
  }
  void pul(int k, int l, int r) {
    int lc = k << 1 | 0, rc = k << 1 | 1;
    t[k].first = (t[lc].first + t[rc].first) % MD;
    t[k].second = (t[lc].second + t[rc].second) % MD;
  }
  void put(int k, int l, int r, int x) {
    swap(t[k].first, t[k].second);
    if (l != r)
      z[k] ^= 1;
  }
  void pus(int k, int l, int r) {
    if (z[k]) {
      int m = (l + r) / 2;
      put(k << 1 | 0, l, m, z[k]), put(k << 1 | 1, m + 1, r, z[k]);
      z[k] = 0;
    }
  }
  void upd(int k, int l, int r, int ql, int qr, int x) {
    if (ql <= l && qr >= r)
      put(k, l, r, x);
    else if (qr >= l && ql <= r) {
      int m = (l + r) / 2;
      pus(k, l, r);
      upd(k << 1 | 0, l, m, ql, qr, x), upd(k << 1 | 1, m + 1, r, ql, qr, x);
      pul(k, l, r);
    }
  }
  void upd(int l, int r, int x) {
    upd(1, 0, n - 1, l, r, x);
  }
};

Lst<100000> st;

int n;

void init(int n_, int m, vi p, vi a) {
  n = n_;
  vector<vi> ej(n + m);
  for (int i = 0; i < n + m; i++)
    if (p[i] != -1)
      ej[p[i]].push_back(i);
  vector<ll> v(n + m), f(n + m);
  vector<pi> c(m);
  function<void(int)> dfs = [&](int i) {
    if (ej[i].size() == 0) {
      f[i] = 1;
      return;
    }
    f[i] = ej[i].size();
    for (int j : ej[i]) {
      dfs(j);
      f[i] = f[i] * f[j] % MD;
    }
    int k = ej[i].size();
    vector<ll> L(k, 1), R(k, 1);
    for (int j = 1; j < k; j++)
      L[j] = L[j - 1] * f[ej[i][j - 1]] % MD;
    for (int j = k - 2; j >= 0; j--)
      R[j] = R[j + 1] * f[ej[i][j + 1]] % MD;
    for (int j = 0; j < k; j++)
      v[ej[i][j]] = L[j] * R[j] % MD;
  };
  v[0] = 1;
  dfs(0);
  for (int i = 1; i < n + m; i++)
    v[i] = v[p[i]] * v[i] % MD;
  for (int i = 0; i < m; i++) {
    int u = v[i + n];
    if (a[i])
      c[i].first = u % MD;
    else
      c[i].second = u % MD;
  }
  st.bld(m, c);
}

int count_ways(int l, int r) {
  st.upd(l - n, r - n, 1);
  return st.t[1].first;
}

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11