Submission #1290400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290400		silentloop	Digital Circuit (IOI22_circuit)	C++20	0 / 100	1356 ms	2162688 KiB

circuit

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

const int MOD = 1000002022;
const int MAXN = 2e5 + 1;

vector<ll> grafo[MAXN];
ll lazy[MAXN];
pair<ll, ll> p[MAXN];
pair<ll, ll> rang[MAXN];

// En los comentarios p es el parametro del nodo

ll c01(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 0 si p es 1
{
  return (a.fr * b.fr) % MOD;
}

ll c02(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 0 si p es 2
{
  return (((a.fr * b.se) % MOD + (a.se * b.fr) % MOD) % MOD + c01(a, b)) % MOD;
}

ll c12(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 1 si p es 2
{
  return (a.se * b.se) % MOD;
}

ll c11(pair<ll, ll> &a, pair<ll, ll> &b) // Cantidad de formas de obtener 1 si p es 1
{
  return (((a.fr * b.se) % MOD + (a.se * b.fr) % MOD) % MOD + c12(a, b)) % MOD;
}

void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
  ll i, j;
  for (i = 1; i < sz(P); i++)
    grafo[P[i]].pb(i);
  for (i = 0; i < sz(A); i++)
  {
    p[i + N] = {!A[i], A[i]};
    rang[i + N] = {i + N, i + N};
  }
  for (i = N - 1; i >= 0; i--)
  {
    ll X = grafo[i][0], Y = grafo[i][1];
    pair<ll, ll> x = p[X], y = p[Y];
    p[i] = {(c01(x, y) + c02(x, y)) % MOD, (c11(x, y) + c12(x, y)) % MOD};
    rang[i] = {min(rang[X].fr, rang[Y].fr), max(rang[X].se, rang[Y].se)};
  }
}

void prop(ll nod)
{
  ll X = grafo[nod][0], Y = grafo[nod][1];
  lazy[X] = (lazy[X] + 1) % 2;
  swap(p[X].fr, p[X].se);

  lazy[Y] = (lazy[Y] + 1) % 2;
  swap(p[Y].fr, p[Y].se);

  lazy[nod]=0;
}

void up(ll nod)
{
  ll X = grafo[nod][0], Y = grafo[nod][1];
  pair<ll, ll> x = p[X], y = p[Y];
  p[nod] = {(c01(x, y) + c02(x, y)) % MOD, (c11(x, y) + c12(x, y)) % MOD};
}

void update(ll l, ll r, ll nod)
{
  if (rang[nod].fr > r || rang[nod].se < l)
    return;
  if (rang[nod].fr >= l && rang[nod].se <= r)
  {
    lazy[nod] = (lazy[nod] + 1) % 2;
    swap(p[nod].fr, p[nod].se);
    return;
  }
  prop(nod);
  update(l, r, nod * 2);
  update(l, r, nod * 2 + 1);
  up(nod);
}

int count_ways(int L, int R)
{
  update(L, R, 0);
  return p[0].se;
}

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