Submission #1234259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234259		trimkus	Digital Circuit (IOI22_circuit)	C++20	52 / 100	353 ms	23584 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 4e5 + 1;
int A[MAXN];
vector<int> adj[MAXN];
int N, M;
array<ll, 2> dp[MAXN];
int lazy[MAXN];
int depth[MAXN];
ll exp(ll a, ll b) {
  ll res = 1;
  while (b  > 0) {
    if (b & 1) {
      res = res * a % MOD;
    }
    a = a * a % MOD;
    b /= 2;
  }
  return res;
}


void upd(int i) {
  if (lazy[i] == 0) return;
  if (2 * i + 1 < MAXN) {
    lazy[i * 2] ^= 1;
    lazy[i * 2 + 1] ^= 1;
  }
  lazy[i] = 0;
  swap(dp[i][0], dp[i][1]);
}

void update(int i, int l, int r, int ql, int qr) {
  upd(i);
  if (ql > r || l > qr) return;
  // cout << l << " " << r << "\n";
  if (ql <= l && r <= qr) {
    lazy[i] ^= 1;
    upd(i);
    return;
  }
  int m = (l + r) / 2;
  update(i * 2, l, m, ql, qr);
  update(i * 2 + 1, m + 1, r, ql, qr);
  dp[i][0] = (dp[i * 2][0] + dp[i * 2 + 1][0]) % MOD;
  dp[i][1] = (dp[i * 2][1] + dp[i * 2 + 1][1]) % MOD;
}
void build(int i, int l, int r) {
  if (l == r) {
      dp[i][A[l + N]] = exp(2, N - depth[l + N]);
      return;
  }
  int m = (l + r) / 2;
  build(i * 2, l, m);
  build(i * 2 + 1, m + 1, r);
  for (int k = 0; k < 2; ++k) {
    dp[i][k] = (dp[i * 2][k] + dp[i * 2 + 1][k]) % MOD;
  }
}

void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
  N = _N;
  M = _M;
  for (int i = N; i < N + M; ++i) {
    A[i + 1] = _A[i - N];
  }
  for (int i = 1; i < N + M; ++i) {
    adj[P[i] + 1].push_back(i + 1);
  }
  auto dfs = [&](auto& dfs, int i) -> void {
    for (auto& u : adj[i]) {
      depth[u] = depth[i] + 1; 
      dfs(dfs, u);
    }
  };
  dfs(dfs, 1);
  build(1, 1, M);
}





int count_ways(int L, int R) {
  // cout << dp[1][1] << " -> ";
  // cout << "[ " << L << " , " << R << " ]:\n";
  L += 1;
  R += 1;
  update(1, 1, M, L - N, R - N);
  // for (int i = 0; i < N + M; ++i) {
  //   cout << i << " = " << dp[i][0] << " " << dp[i][1] << "\n";
  // }
  // cout << "\n";
  // for (int i = 0; i < N + M; ++i) {
  //   // update(0, 0, M - 1, i, i);
  //   cout << lazy[i] << " ";
  // }
  // cout << "\n";
  return dp[1][1];
}

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