Submission #628440

#	Time	Username	Problem	Language	Result	Execution time	Memory
628440		abeker	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1779 ms	26912 KiB

circuit

#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;

const int MOD = 1e9 + 2022;

inline int add(int x, int y) {
  x += y;
  if (x >= MOD)
    return x - MOD;
  if (x < 0)
    return x + MOD;
  return x;
}

inline int mul(int x, int y) {
  return (long long)x * y % MOD;
}

struct Node {
  int tot, sum, lazy;
  Node(int tot, int sum, int lazy) : tot(tot), sum(sum), lazy(lazy) {}
  Node() : tot(0), sum(0), lazy(0) {}
};

class Tournament {
  int m, offset;
  vector <Node> tour;
public:
  Node merge(Node lhs, Node rhs) {
    return Node(add(lhs.tot, rhs.tot), add(lhs.sum, rhs.sum), 0);
  }
  void refresh(int x) {
    tour[x] = merge(tour[2 * x], tour[2 * x + 1]);
  }
  Tournament(int m, int n, vector <int> v, vector <int> s) : m(m) {
    for (offset = 1; offset < n; offset *= 2);
    tour.resize(2 * offset);
    for (int i = 0; i < n; i++)
      tour[i + offset] = Node(v[i], s[i] * v[i], 0);
    for (int i = offset - 1; i; i--)
      refresh(i);
  }
  Tournament() {}
  void prop(int x) {
    if (!tour[x].lazy)
      return;
    tour[x].sum = add(tour[x].tot, -tour[x].sum);
    if (x < offset) {
      tour[2 * x].lazy ^= 1;
      tour[2 * x + 1].lazy ^= 1;
    }
    tour[x].lazy = 0;
  }
  void update(int x, int lo, int hi, int from, int to) {
    prop(x);
    if (lo >= to || hi <= from)
      return;
    if (lo >= from && hi <= to) {
      tour[x].lazy ^= 1;
      prop(x);
      return;
    }
    int mid = (lo + hi) / 2;
    update(2 * x, lo, mid, from, to);
    update(2 * x + 1, mid, hi, from, to);
    refresh(x);
  }
  void update(int from, int to) {
    update(1, 0, offset, from - m, to - m);
  }
  int query() {
    prop(1);
    return tour[1].sum;
  }
};

Tournament solver;

void init(int N, int M, vector <int> p, vector <int> a) {
  vector <int> pos(N + M);
  vector <vector <int>> ch(N);
  for (int i = 1; i < N + M; i++) {
    pos[i] = ch[p[i]].size();
    ch[p[i]].push_back(i);
  }
  vector <int> sz(N), sub(N + M, 1);
  for (int i = 0; i < N; i++)
    sz[i] = sub[i] = ch[i].size();
  for (int i = N - 1; i; i--)
    sub[p[i]] = mul(sub[p[i]], sub[i]);   
  vector <vector <int>> pref(N), suff(N);
  for (int i = 0; i < N; i++) {
    pref[i].resize(sz[i]);
    suff[i].resize(sz[i]);
    for (int j = 0; j < sz[i]; j++)
      pref[i][j] = mul(j ? pref[i][j - 1] : 1, sub[ch[i][j]]);
    for (int j = sz[i] - 1; j >= 0; j--)
      suff[i][j] = mul(j < sz[i] - 1 ? suff[i][j + 1] : 1, sub[ch[i][j]]);
  }
  vector <int> prod(N + M);
  prod[0] = 1;
  for (int i = 1; i < N + M; i++)
    prod[i] = mul(prod[p[i]], mul(pos[i] ? pref[p[i]][pos[i] - 1] : 1, pos[i] < sz[p[i]] - 1 ? suff[p[i]][pos[i] + 1] : 1));
  solver = Tournament(N, M, vector <int> (prod.begin() + N, prod.end()), a);
}

int count_ways(int l, int r) {
  solver.update(l, r + 1);
  return solver.query();
}

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