Submission #1231374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231374		LeonidCuk	Digital Circuit (IOI22_circuit)	C++20	100 / 100	352 ms	33688 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long mod=1e9+2022;
struct node{
  long long sum=0,sga=0,lazy=0;
};
vector<vector<int>>g;
vector<long long>tot,klk,crnoilbelo;
vector<node>st;
void dfs(int a,int b,long long sum)
{
  if(a>=n)
  {
    klk[a-n]=sum;
    return;
  }
  vector<long long>suf(g[a].size());
  long long pref=1;
  for(int i=suf.size()-1;i>=0;i--)
  {
       suf[i]=(tot[g[a][i]]*pref)%mod;
       pref=pref*tot[g[a][i]]%mod;
  }
  pref=1;
  for(int i=0;i<g[a].size();i++)
  {
    if(i==g[a].size()-1)dfs(g[a][i],a,(sum*pref)%mod);
    else
    {
      dfs(g[a][i],a,sum*pref%mod*suf[i+1]%mod);
    }
    pref=pref*tot[g[a][i]]%mod;
  }
}
void build(int i,int l,int r)
{
  if(l==r)
  {
    st[i].sum=klk[l];
    if(crnoilbelo[l]==1)st[i].sga=klk[l];
    return;
  }
  int m1=(l+r)/2;
  build(2*i,l,m1);
  build(2*i+1,m1+1,r);
  st[i].sum=(st[2*i].sum+st[2*i+1].sum)%mod;
  st[i].sga=(st[2*i].sga+st[2*i+1].sga)%mod;
}
void update(int i,int l,int r,int tl,int tr)
{
  if(st[i].lazy==1)
  {
    st[i].sga=(st[i].sum-st[i].sga+mod)%mod;
    st[i].lazy=0;
    if(l!=r)
    {
      st[2*i].lazy^=1;
      st[2*i+1].lazy^=1;
    }
  }
  if(l>r||tl>r||l>tr)return;
  if(tl<=l&&r<=tr)
  {
    st[i].sga=(st[i].sum-st[i].sga+mod)%mod;
    if(l!=r)
    {
      st[2*i].lazy^=1;
      st[2*i+1].lazy^=1;
    }
    return;
  }
  int m1=(l+r)/2;
  update(2*i,l,m1,tl,tr);
  update(2*i+1,m1+1,r,tl,tr);
  st[i].sga=(st[2*i].sga+st[2*i+1].sga)%mod;
}
void init(int N, int M,vector<int> P,vector<int> A) {
  n=N;m=M;
  for(auto i:A)crnoilbelo.push_back(i);
  g.resize(n);
  klk.resize(m);
  for(int i=1;i<P.size();i++)
  {
    g[P[i]].push_back(i);
  }
  tot.resize(n+m,1);
  for(int i=n-1;i>=0;i--)
  {
    for(auto j:g[i])
    {
      tot[i]=(tot[i]*tot[j])%mod;
    }
    tot[i]=(tot[i]*g[i].size())%mod;
  }
  dfs(0,0,1);
  st.resize(4*m+1);
  build(1,0,m-1);
}

int count_ways(int L, int R) {
  update(1,0,m-1,L-n,R-n);
  return st[1].sga;
}

• 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