Submission #914471

#	Time	Username	Problem	Language	Result	Execution time	Memory
914471		ALTAKEXE	Digital Circuit (IOI22_circuit)	C++17	52 / 100	708 ms	50768 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
const ll MOD = 1000002022;
int n, m;
ll p[10000001], sz[10000001], v[1000001], d1[2000001], d2[2000001];
bool lz[2000001];
vector<ll> d[1000001];
void dfs(int u)
{
  for (auto v : d[u])
  {
    sz[v] = sz[u] + 1;
    dfs(v);
  }
}
void build(int l, int r, int i, vector<int> &t)
{
  if (l == r)
  {
    if (t[l])
    {
      d1[i] = v[l];
    }
    else
    {
      d2[i] = v[l];
    }
    return;
  }
  int md = (l + r) / 2;
  build(l, md, 2 * i, t);
  build(md + 1, r, 2 * i + 1, t);
  d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
  d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void lazy(int l, int r, int i)
{
  if (!lz[i])
    return;
  lz[i] = 0;
  swap(d1[i], d2[i]);
  if (l == r)
    return;
  lz[2 * i] = !lz[2 * i];
  lz[2 * i + 1] = !lz[2 * i + 1];
}
void update(int l, int r, int i, int ql, int qr)
{
  lazy(l, r, i);
  if (r < ql || qr < l)
    return;
  if (ql <= l && r <= qr)
  {
    lz[i] = 1;
    lazy(l, r, i);
    return;
  }
  int md = (l + r) / 2;
  update(l, md, 2 * i, ql, qr);
  update(md + 1, r, 2 * i + 1, ql, qr);
  d1[i] = (d1[2 * i] + d1[2 * i + 1]) % MOD;
  d2[i] = (d2[2 * i] + d2[2 * i + 1]) % MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
  p[0] = 1;
  n = N;
  m = M;
  for (int i = 1; i < N + M; i++)
    p[i] = (p[i - 1] * 2) % MOD;
  for (int i = 1; i < N + M; i++)
    d[P[i]].push_back(i);
  dfs(0);
  for (int i = N; i < N + M; i++)
    v[i - N] = p[N - sz[i]];
  build(0, M - 1, 1, A);
}
 
int count_ways(int L, int R)
{
  update(0, m - 1, 1, L - n, R - n);
  return d1[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