Submission #1270372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270372		rxlfd314	Digital Circuit (IOI22_circuit)	C++20	100 / 100	328 ms	33696 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100005, MOD = 1000002022;
int N, M, contrib[mxN<<1], tot[mxN<<1];
vt<int> P, A, adj[mxN<<1];

int lz[mxN<<2], st[mxN<<2][2];

#define lc i << 1
#define rc lc | 1

void Apply(const int i) {
  lz[i] ^= 1;
  swap(st[i][0], st[i][1]);
}

void pull(const int i) {
  FOR(j, 0, 1)
    st[i][j] = (st[lc][j] + st[rc][j]) % MOD;
}

void push(const int i) {
  if (!lz[i])
    return;
  Apply(lc), Apply(rc);
  lz[i] = 0;
}

void build(const int i = 1, const int tl = 0, const int tr = M-1) {
  if (tl == tr) {
    st[i][1] = A[tl] * contrib[tl+N];
    st[i][0] = !A[tl] * contrib[tl+N];
    return;
  }
  const int tm = tl + tr >> 1;
  build(lc, tl, tm);
  build(rc, tm+1, tr);
  pull(i);
}

void update(const int ql, const int qr, const int i = 1, const int tl = 0, const int tr = M-1) {
  if (tl > qr || tr < ql)
    return;
  if (ql <= tl && tr <= qr)
    Apply(i);
  else {
    push(i);
    const int tm = tl + tr >> 1;
    update(ql, qr, lc, tl, tm);
    update(ql, qr, rc, tm+1, tr);
    pull(i);
  }
}

void init(int _N, int _M, vt<int> _P, vt<int> _A) {
  N = _N, M = _M, P = _P, A = _A;
  FOR(i, 1, N+M-1)
    adj[P[i]].push_back(i);
  const auto dfs = [&](auto &&self, const int i) -> void {
    tot[i] = max(size(adj[i]), 1);
    for (const auto &j : adj[i]) {
      self(self, j);
      tot[i] = 1ll * tot[i] * tot[j] % MOD;
    }
  };
  dfs(dfs, 0);
  const auto dfs2 = [&](auto &&self, const int i) -> void {
    if (i >= N)
      return;
    vt<int> pre(size(adj[i])+1, 1), suf(size(adj[i])+2, 1);
    FOR(j, 0, size(adj[i])-1)
      pre[j+1] = 1ll * pre[j] * tot[adj[i][j]] % MOD;
    ROF(j, size(adj[i])-1, 0)
      suf[j+1] = 1ll * suf[j+2] * tot[adj[i][j]] % MOD;
    FOR(j, 0, size(adj[i])-1) {
      contrib[adj[i][j]] = 1ll * contrib[i] * pre[j] % MOD * suf[j+2] % MOD;
      self(self, adj[i][j]);
    }
  };
  contrib[0] = 1;
  dfs2(dfs2, 0);
  build();
}

int count_ways(const int L, const int R) {
  update(L - N, R - N);
  return st[1][1];
}

• 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