Submission #630163

#	Time	Username	Problem	Language	Result	Execution time	Memory
630163		CyanForces	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1127 ms	42520 KiB

circuit

#include "circuit.h"

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;

vi a;
int n,m;
vector<ll> contrib;
vector<ll> contrib_pref;
const ll mod = ll(1e9) + 2022;


//from atcoder

int ceil_pow2(int n) {
  int x = 0;
  while ((1U << x) < (unsigned int)(n)) x++;
  return x;
}

template <class S,
         S (*op)(S, S),
         S (*e)(),
         class F,
         S (*mapping)(F, S),
         F (*composition)(F, F),
         F (*id)()>
         struct lazy_segtree {
           public:
             lazy_segtree() : lazy_segtree(0) {}
             lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
             lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
               log = ceil_pow2(_n);
               size = 1 << log;
               d = std::vector<S>(2 * size, e());
               lz = std::vector<F>(size, id());
               for (int i = 0; i < _n; i++) d[size + i] = v[i];
               for (int i = size - 1; i >= 1; i--) {
                 update(i);
               }
             }

             void set(int p, S x) {
               assert(0 <= p && p < _n);
               p += size;
               for (int i = log; i >= 1; i--) push(p >> i);
               d[p] = x;
               for (int i = 1; i <= log; i++) update(p >> i);
             }

             S get(int p) {
               assert(0 <= p && p < _n);
               p += size;
               for (int i = log; i >= 1; i--) push(p >> i);
               return d[p];
             }

             S prod(int l, int r) {
               assert(0 <= l && l <= r && r <= _n);
               if (l == r) return e();

               l += size;
               r += size;

               for (int i = log; i >= 1; i--) {
                 if (((l >> i) << i) != l) push(l >> i);
                 if (((r >> i) << i) != r) push(r >> i);
               }

               S sml = e(), smr = e();
               while (l < r) {
                 if (l & 1) sml = op(sml, d[l++]);
                 if (r & 1) smr = op(d[--r], smr);
                 l >>= 1;
                 r >>= 1;
               }

               return op(sml, smr);
             }

             S all_prod() { return d[1]; }

             void apply(int p, F f) {
               assert(0 <= p && p < _n);
               p += size;
               for (int i = log; i >= 1; i--) push(p >> i);
               d[p] = mapping(f, d[p]);
               for (int i = 1; i <= log; i++) update(p >> i);
             }
             void apply(int l, int r, F f) {
               assert(0 <= l && l <= r && r <= _n);
               if (l == r) return;

               l += size;
               r += size;

               for (int i = log; i >= 1; i--) {
                 if (((l >> i) << i) != l) push(l >> i);
                 if (((r >> i) << i) != r) push((r - 1) >> i);
               }

               {
                 int l2 = l, r2 = r;
                 while (l < r) {
                   if (l & 1) all_apply(l++, f);
                   if (r & 1) all_apply(--r, f);
                   l >>= 1;
                   r >>= 1;
                 }
                 l = l2;
                 r = r2;
               }

               for (int i = 1; i <= log; i++) {
                 if (((l >> i) << i) != l) update(l >> i);
                 if (((r >> i) << i) != r) update((r - 1) >> i);
               }
             }

             template <bool (*g)(S)> int max_right(int l) {
               return max_right(l, [](S x) { return g(x); });
             }
             template <class G> int max_right(int l, G g) {
               assert(0 <= l && l <= _n);
               assert(g(e()));
               if (l == _n) return _n;
               l += size;
               for (int i = log; i >= 1; i--) push(l >> i);
               S sm = e();
               do {
                 while (l % 2 == 0) l >>= 1;
                 if (!g(op(sm, d[l]))) {
                   while (l < size) {
                     push(l);
                     l = (2 * l);
                     if (g(op(sm, d[l]))) {
                       sm = op(sm, d[l]);
                       l++;
                     }
                   }
                   return l - size;
                 }
                 sm = op(sm, d[l]);
                 l++;
               } while ((l & -l) != l);
               return _n;
             }

             template <bool (*g)(S)> int min_left(int r) {
               return min_left(r, [](S x) { return g(x); });
             }
             template <class G> int min_left(int r, G g) {
               assert(0 <= r && r <= _n);
               assert(g(e()));
               if (r == 0) return 0;
               r += size;
               for (int i = log; i >= 1; i--) push((r - 1) >> i);
               S sm = e();
               do {
                 r--;
                 while (r > 1 && (r % 2)) r >>= 1;
                 if (!g(op(d[r], sm))) {
                   while (r < size) {
                     push(r);
                     r = (2 * r + 1);
                     if (g(op(d[r], sm))) {
                       sm = op(d[r], sm);
                       r--;
                     }
                   }
                   return r + 1 - size;
                 }
                 sm = op(d[r], sm);
               } while ((r & -r) != r);
               return 0;
             }

           private:
             int _n, size, log;
             std::vector<S> d;
             std::vector<F> lz;

             void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
             void all_apply(int k, F f) {
               d[k] = mapping(f, d[k]);
               if (k < size) lz[k] = composition(f, lz[k]);
             }
             void push(int k) {
               all_apply(2 * k, lz[k]);
               all_apply(2 * k + 1, lz[k]);
               lz[k] = id();
             }
         };


struct S { ll on, off; };
S op(S a, S b) { return S{a.on + b.on, a.off + b.off}; }
S e() { return S{0,0}; }

using F = bool;
F id() { return 0; }
F composition(F f, F g) { return f^g; }
S mapping(F f, S s) { return f ? S{s.off, s.on} : s; }

using tree = lazy_segtree<S,op,e,F,mapping,composition,id>;

unique_ptr<tree> t;

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
  n = N, m = M;
  contrib.assign(m,0);
  a = A;

  vector<vi> g(n+m);
  rep(i,1,n+m) g[P[i]].emplace_back(i);



  vector<ll> ways(n);

  function<void(int,int)> dfs = [&](int x, int p) {
    ways[x] = sz(g[x]);
    for(int y : g[x]) if(y != p && y < n) {
      dfs(y,x);
      ways[x] = ways[x] * ways[y] % mod;
    }
  };
  dfs(0,-1);


  function<void(int,int,ll)> go = [&](int x, int p, ll prod) {
    if(x >= n) {
      contrib[x-n] = prod;
      return;
    }
    vector<ll> c;
    for(int y : g[x]) if(y != p && y < n) {
      c.emplace_back(ways[y]);
    }
    vector<ll> pref(sz(c)+1,1), suf(sz(c)+1,1);
    rep(i,0,sz(c)) pref[i+1] = pref[i] * c[i] % mod;
    rep(i,0,sz(c)) suf[i+1] = suf[i] * c[sz(c)-i-1] % mod;
    int before = 0, after = sz(c);
    for(int y : g[x]) if(y != p) {
      if(y < n) --after;
      ll q = pref[before] * suf[after] % mod;
      go(y, x, q * prod % mod);
      if(y < n) ++before;
    }
    assert(after == 0 && before == sz(c));
  };
  go(0,-1,1);

  t = make_unique<tree>(m);
  rep(i,0,m) t->set(i,S{0,contrib[i]});
  rep(i,0,m) if(a[i]) t->apply(i,true);
}

int count_ways(int L, int R) {
  int l = L - n;
  int r = R - n + 1;
  t->apply(l,r,true);
  ll ans = t->all_prod().on;
  return int(ans % mod);
}

• 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