Submission #797204

#	Time	Username	Problem	Language	Result	Execution time	Memory
797204		penguinman	Digital Circuit (IOI22_circuit)	C++17	100 / 100	929 ms	44000 KiB

circuit

#include "circuit.h"

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

constexpr ll mod = 1'000'002'022;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define all(a) a.begin(),a.end()
#define pb emplace_back
#define ln "\n"

struct lazy_segment_tree{
  ll N;
  vi node;
  vector<bool> flag;
  vi sum;
  lazy_segment_tree(ll n, vi s, vi a){
    N = 1;
    while(N <= n) N *= 2;
    node.resize(2*N);
    flag.resize(2*N);
    sum.resize(2*N);
    rep(i,0,n) sum[i+N] = s[i];
    per(i,N-1,1) sum[i] = (sum[i*2]+sum[i*2+1])%mod;
    rep(i,0,n) node[i+N] = s[i]*a[i];
    per(i,N-1,1) node[i] = (node[i*2]+node[i*2+1])%mod;
  };
  void eval(ll now){
    if(flag[now]){
      node[now] = sum[now]-node[now];
      if(now < N){
        flag[now*2] = !flag[now*2];
        flag[now*2+1] = !flag[now*2+1];
      }
      flag[now] = false;
    }
  }
  void update(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
    if(r == -1) r = N;
    eval(now);
    if(a <= l && r <= b){
      flag[now] = !flag[now];
      eval(now);
      return;
    }
    if(r <= a || b <= l) return;
    update(a,b,now*2,l,(l+r)/2);
    update(a,b,now*2+1,(l+r)/2,r);
    node[now] = (node[now*2]+node[now*2+1])%mod;
  }
  ll calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
    if(r == -1) r = N;
    eval(now);
    if(a <= l && r <= b) return node[now];
    if(r <= a || b <= l) return 0;
    return (calc(a,b,now*2,l,(l+r)/2)+calc(a,b,now*2+1,(l+r)/2,r))%mod;
  }
};

vi sum;
vii edge;
vi A;
ll N,M;
lazy_segment_tree seg(0,vi(),vi());

void init(int n, int m, std::vector<int> P, std::vector<int> a) {
  N = n, M = m;
  sum.resize(N+M,1);
  edge.resize(N+M);
  A.resize(N+M);
  rep(i,0,M) A[i+N] = a[i];
  rep(i,1,N+M){
    edge[P[i]].pb(i);
  }
  vi sum2(N+M);
  std::function<void(ll)> dfs1 = [&](ll now){
    sum2[now] = edge[now].size();
    sum2[now] = std::max(sum2[now], 1ll);
    for(auto next: edge[now]){
      dfs1(next);
      sum2[now] *= sum2[next];
      sum2[now] %= mod;
    }
  };
  dfs1(0);
  std::function<void(ll)> dfs2 = [&](ll now){
    ll len = edge[now].size();
    vi l(len+1,1), r(len+1,1);
    rep(i,0,len){
      l[i+1] = l[i]*sum2[edge[now][i]]%mod;
    }
    per(i,len-1,0){
      r[i] = r[i+1]*sum2[edge[now][i]]%mod;
    }
    rep(i,0,len){
      ll next = edge[now][i];
      sum[next] = sum[now]*l[i]%mod*r[i+1]%mod;
      dfs2(next);
    }
  };
  dfs2(0);
  vi sum_(M);
  rep(i,0,M) sum_[i] = sum[i+N];
  vi A_(M);
  rep(i,0,M) A_[i] = a[i];
  lazy_segment_tree seg2(M,sum_,A_);
  seg = seg2;
}

int count_ways(int L, int R) {
  L -= N;
  R -= N;
  seg.update(L,R+1);
  ll ans = seg.calc(0,M);
  if(ans < 0) ans += mod;
  ans %= mod;
  return ans;
}

• 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