Submission #1234220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234220		trimkus	Digital Circuit (IOI22_circuit)	C++20	16 / 100	341 ms	11044 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 2e5 + 1;
int A[MAXN];
vector<int> adj[MAXN];
int N, M;
array<ll, 2> dp[MAXN];
int lazy[MAXN];

void mrg(int i) {
    int j = i * 2 + 1;
    int k = i * 2 + 2;
    ll now = dp[j][0] * dp[k][1] % MOD;
    now = (now + (dp[j][1] * dp[k][0]) % MOD) % MOD;
    dp[i][1] = now;
    dp[i][0] = now;
    now = (2LL * dp[j][0] * dp[k][0]) % MOD;
    dp[i][0] = (dp[i][0] + now) % MOD;
    now = (2LL * dp[j][1] * dp[k][1]) % MOD;
    dp[i][1] = (dp[i][1] + now) % MOD;
    // cout << i << " " << dp[i][1] << " " << dp[i][0] << "\n";

}

void upd(int i) {
  if (lazy[i] == 0) return;
  if (2 * i + 2 < MAXN) {
    lazy[i * 2 + 1] ^= 1;
    lazy[i * 2 + 2] ^= 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;
  }
  // upd(i);
  int m = (l + r) / 2;
  update(i * 2 + 1, l, m, ql, qr);
  update(i * 2 + 2, m + 1, r, ql, qr);
  mrg(i);
}


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] = _A[i - N];
  }
  for (int i = 1; i < N + M; ++i) {
    adj[P[i]].push_back(i);
  }
  auto dfs = [&](auto& dfs, int i) -> void {
    if (i >= N) {
      // cout << i << " " << A[i] << "\n";
        dp[i][A[i]] = 1;
        dp[i][1 ^ A[i]] = 0;
        return;
    }
    dfs(dfs, i * 2 + 1);
    dfs(dfs, i * 2 + 2);
    mrg(i);
  };
  dfs(dfs, 0);
}





int count_ways(int L, int R) {
  // cout << dp[1][1] << " -> ";
  // cout << "[ " << L << " , " << R << " ]:\n";
  update(0, 0, M - 1, 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[0][1];
}

• 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