Submission #812890

#	Time	Username	Problem	Language	Result	Execution time	Memory
812890		blackyuki	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1049 ms	23588 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
const ll mod=1000002022;
#include "circuit.h"

struct segtree{
  ll N=1;
  vi seg,lazy,sum;
  ll f(ll a,ll b){
    return (a+b)%mod;
  }
  void init(vi a,vi b){
    while(N<a.size())N<<=1;
    seg=vi(N*2);lazy=vi(N*2);sum=vi(N*2);
    rep(i,a.size()){
      sum[i+N]=a[i];
      seg[i+N]=a[i]*b[i];
    }
    for(ll i=N-1;i>0;i--){
      sum[i]=f(sum[i*2],sum[i*2+1]);
      seg[i]=f(seg[i*2],seg[i*2+1]);
    }
  }
  void eval(ll k,ll l,ll r){
    if(!lazy[k])return;
    seg[k]=(sum[k]-seg[k])%mod;
    if(r-l>1)rep(t,2)lazy[k*2+t]^=1;
    lazy[k]=0;
  }
  ll get(){
    eval(1,0,N);
    return seg[1];
  }
  void upd(ll a,ll b,ll k=1,ll l=0,ll r=-1){
    if(r==-1)r=N;
    if(a<=l&&r<=b){
      lazy[k]^=1;eval(k,l,r);return;
    }
    if(r<=a||b<=l){
      eval(k,l,r);return;
    }
    eval(k,l,r);
    upd(a,b,k*2,l,(l+r)/2);
    upd(a,b,k*2+1,(l+r)/2,r);
    seg[k]=f(seg[k*2],seg[k*2+1]);
  }
};
segtree seg;
ll n,N_;
void init(int N, int M, std::vector<int> P, std::vector<int> A){
  N_=N;
  vvi ch(N+M);
  REP(i,1,N+M)ch[P[i]].pb(i);
  vi prod(N+M,1);
  for(ll i=N-1;i>=0;i--){
    prod[i]=ch[i].size();
    for(ll x:ch[i])prod[i]=prod[i]*prod[x]%mod;
  }
  vi dp(N+M,1);
  rep(i,N){
    vi tl(ch[i].size()+1,1),tr(ch[i].size()+1,1);
    rep(j,ch[i].size())tl[j+1]=tl[j]*prod[ch[i][j]]%mod;
    for(ll j=ch[i].size()-1;j>=0;j--)tr[j]=tr[j+1]*prod[ch[i][j]]%mod;
    rep(j,ch[i].size())dp[ch[i][j]]=dp[i]*tl[j]%mod*tr[j+1]%mod;
  }
  n=M;
  vi a(n),b(n);
  rep(i,n)a[i]=dp[N+i];
  rep(i,n)b[i]=A[i];
  seg.init(a,b);
}

int count_ways(int L, int R) {
  ll l=L-N_,r=R+1-N_;
  seg.upd(l,r);
  ll ans=seg.get();
  if(ans<0)ans+=mod;
  return ans;
}

Compilation message (stderr)

circuit.cpp: In member function 'void segtree::init(vi, vi)':
circuit.cpp:32:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while(N<a.size())N<<=1;
      |           ~^~~~~~~~~

• 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