Submission #1216499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216499		user736482	Digital Circuit (IOI22_circuit)	C++20	100 / 100	345 ms	21144 KiB

circuit

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000002022
#define INF 1000000019
#define POT (1<<20)
#define INFL 1000000000000000099
ll n,m;
ll par[200007],vl[200007],ost[200007];
vector<ll>d[200007];
ll sm;
ll sgtree[POT];
bool inv[POT];
void spych(ll v){
    if(!inv[v])return;
    inv[v*2]^=1;
    inv[v*2+1]^=1;
    sgtree[v*2]*=-1;
    sgtree[v*2+1]*=-1;
    inv[v]=0;
}
void ch(ll v,ll l,ll r,ll pocz,ll kon){
    if(l>kon || r<pocz)return;
    if(l>=pocz && r<=kon){sgtree[v]*=-1;inv[v]^=1;}
    else{spych(v);ch(v*2,l,(l+r)/2,pocz,kon);ch(v*2+1,(l+r)/2+1,r,pocz,kon);sgtree[v]=sgtree[v*2]+sgtree[v*2+1];}
}
void init(int N,int M,vector<int>p,vector<int>a){
    n=N+M;
    m=M;
    for(ll i=1;i<n;i++){
        par[i]=p[i];
        d[p[i]].pb(i);
    }
    for(ll i=0;i<n;i++){
        vl[i]=max(1,(int)d[i].size());
    }
    for(ll i=n-1;i>=0;i--){
        for(ll j : d[i])vl[i]=(vl[i]*vl[j])%MOD;
    }
    ost[0]=1;
    for(ll i=0;i<n-m;i++){
        vector<ll>v1={1},v2={1};
        for(ll j=0;j<d[i].size();j++)v1.pb((v1.back()*vl[d[i][j]])%MOD);
        for(ll j=d[i].size()-1;j>=0;j--)v2.pb((v2.back()*vl[d[i][j]])%MOD);
        for(ll j=0;j<d[i].size();j++){
            ost[d[i][j]]=(ost[i]*v1[j])%MOD*v2[d[i].size()-j-1];ost[d[i][j]]%=MOD;
        }
    }
    for(ll i=n-m;i<n;i++)sgtree[i+POT/2-n+m]=-ost[i];
    for(ll i=POT/2-1;i>0;i--)sgtree[i]=sgtree[i*2]+sgtree[i*2+1];
    for(ll i=n-m;i<n;i++){sm+=ost[i];if(a[i-n+m])ch(1,1,POT/2,i-n+m+1,i-n+m+1);}
}
int count_ways(int l,int r){
    ch(1,1,POT/2,l-n+m+1,r-n+m+1);
    return ((sgtree[1]+sm)/2)%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