Submission #643498

#	Time	Username	Problem	Language	Result	Execution time	Memory
643498		Vanilla	Digital Circuit (IOI22_circuit)	C++17	52 / 100	1022 ms	20552 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
typedef long long int64;
using namespace std;
const int64 mod = 1000002022;
const int maxn = 2e5 + 2;
vector <int> ad [maxn];
int64 depth[maxn];
int64 dp[4 * maxn]; // each node contributes 2^(N - depth)
int64 pref[4 * maxn];
int64 lazy[4 * maxn];
int64 pw [maxn];
int n,m;

void dfs (int x) {
  for (int v: ad[x]) {
    depth[v] = depth[x] + 1;
    dfs(v);
  }
}

int64 sum (int l, int r) {
  return (pref[r] - pref[l - 1] + mod) % mod;
}

void push (int x, int l, int r) {
  if (!lazy[x]) return;
  int mid = (l + r) / 2;
  dp[x * 2 + 1] = (sum(l, mid) - dp[x * 2 + 1] + mod) % mod;
  dp[x * 2 + 2] = (sum(mid + 1, r) - dp[x * 2 + 2] + mod) % mod;
  lazy[x * 2 + 1] = !lazy[x * 2 + 1];
  lazy[x * 2 + 2] = !lazy[x * 2 + 2];
  lazy[x] = 0;
}


void upd (int x, int l, int r, int il, int ir) {
  // cout << x << " " << l << " " << r << " " << il << " " << ir << "\n";
  if (il <= l && r <= ir) {
    // cout << l << " " << r << " " << sum(l, r) << "\n";
    dp[x] = (sum(l, r) - dp[x] + mod) % mod;
    lazy[x] = !lazy[x];
    return;
  }
  if (l > ir || r < il) return;
  push(x, l, r);
  int mid = (l + r) / 2;
  upd(x * 2 + 1, l, mid, il, ir);
  upd(x * 2 + 2, mid + 1, r, il, ir);
  dp[x] = (dp[x * 2 + 1] + dp[x * 2 + 2]) % mod;
}
 
void init(int N, int M, vector<int> P, vector<int> A) {
  n = N, m = M;
  pw[0] = 1;
  for (int i = 1; i < maxn; i++){
    pw[i] = pw[i-1] * 2 % mod;
  }
  for (int i = 1; i < N + M; i++){
    ad[P[i]].push_back(i);
  }
  dfs(0);
  for (int i = 0; i < M; i++){
    pref[i] = ((i ? pref[i-1]: 0) + pw[N - depth[i + N]] )% mod;
  }
  for (int i = 0; i < M; i++){
    if (A[i]) upd(0, 0, M - 1, i, i);
  }
}

int count_ways(int L, int R) {
  upd(0, 0, m - 1, L - n, R - n);
  return dp[0];
}

• 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