Submission #813213

#	Time	Username	Problem	Language	Result	Execution time	Memory
813213		kwongweng	Digital Circuit (IOI22_circuit)	C++17	46 / 100	835 ms	20956 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

ll MOD = 1e9 + 2022;
int n, m;
vi g[200000];
vector<ll> prod(100000);
vector<ll> b(100000);
vi a;

void get_prod(int u){
  prod[u]=max(1,(int)g[u].size());
  for (int v : g[u]){
    get_prod(v);
    prod[u] *= prod[v]; prod[u] %= MOD;
  }
}

void dfs(int u, ll val){
  int len = g[u].size();
  if (len==0){
    b[u-n] = val; return;
  }
  vector<ll> p(len);
  FOR(i,0,len){
    p[i] = prod[g[u][i]];
  }
  vector<ll> pre(len+1), suf(len+1);
  pre[0]=1; FOR(i,1,len+1){
    pre[i]=(pre[i-1]*p[i-1]) % MOD;
  }
  suf[len]=1; ROF(i,len-1,0){
    suf[i]=(suf[i+1]*p[i]) % MOD;
  }
  FOR(i,0,len){
    int v = g[u][i];
    ll Val = (pre[i]*suf[i+1]) % MOD;
    Val *= val; Val %= MOD;
    dfs(v,Val);
  }
}

ll ans=0;
struct segtree{
  int sz; vi neg; vector<ll> sm;
  void build(int v, int tl, int tr){
    if (tl==tr){
      if (a[tl]==0) sm[v]=MOD-b[tl];
      else sm[v]=b[tl];
      return;
    }
    int tm = (tl+tr)/2;
    build(2*v,tl,tm); build(2*v+1,tm+1,tr);
    sm[v]=(sm[2*v]+sm[2*v+1]) % MOD;
  }
  void init(int n){
    sz=n; neg.assign(4*n,1); sm.assign(4*n,0);
    build(1,0,sz-1);
  }
  void update(int v, int tl, int tr, int l, int r){
    if (tl != tr && neg[v]==-1){
      neg[2*v]=-neg[2*v]; sm[2*v]=MOD-sm[2*v];
      neg[2*v+1]=-neg[2*v+1]; sm[2*v+1]=MOD-sm[2*v+1];
      neg[v]=1;
    }
    if (tl==l && tr==r){
      neg[v]=-neg[v]; sm[v]=MOD-sm[v]; return;
    }
    if (l>r) return;
    int tm = (tl+tr)/2;
    update(2*v,tl,tm,l,min(r,tm)); update(2*v+1,tm+1,tr,max(l,tm+1),r);
    sm[v]=(sm[2*v]+sm[2*v+1]) % MOD;
  }
  void update(int l, int r){update(1,0,sz-1,l,r);}

  ll get(int v, int tl, int tr, int l, int r){
    if (tl != tr && neg[v]==-1){
      neg[2*v]=-neg[2*v]; sm[2*v]=MOD-sm[2*v];
      neg[2*v+1]=-neg[2*v+1]; sm[2*v+1]=MOD-sm[2*v+1];
      neg[v]=1;
    }
    if (tl==l && tr==r) return sm[v];
    if (l>r) return 0;
    int tm = (tl+tr)/2;
    ll val = (get(2*v,tl,tm,l,min(r,tm))+get(2*v+1,tm+1,tr,max(l,tm+1),r)) % MOD;
    sm[v]=(sm[2*v]+sm[2*v+1])%MOD;
    return val;
  }

  ll get(int l, int r){return get(1,0,sz-1,l,r);}
};

segtree st;

void init(int N, int M, vi P, vi A) {
  n=N, m=M; a=A;
  FOR(i,1,n+m){
    g[P[i]].pb(i);
  }
  get_prod(0); dfs(0,1);
  //FOR(i,0,m) cout << a[i] << " ";
  //cout << '\n';
  //FOR(i,0,m) cout << b[i] << " ";
  //cout << '\n';
  st.init(m);
  FOR(i,0,m){
    if (a[i]){ans += b[i]; ans %= MOD;}
  }
}

int count_ways(int L, int R) {
  st.update(L-n,R-n);
  //FOR(i,0,m) cout << st.get(i,i) << " ";
  //cout << '\n';
  ans += st.get(L-n,R-n);
  ans %= MOD;
  return ans;
}

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