Submission #681114

#	Time	Username	Problem	Language	Result	Execution time	Memory
681114		AngusWong	Digital Circuit (IOI22_circuit)	C++17	100 / 100	1223 ms	45380 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;

const ll mod=1e9+2022;
const ll N=2e5+9;
ll n, m, a[N], pw[N], cnt[N], ps[N], seg[N*4], lazy[N*4], ans=0;
vector<ll> v[N], pre[N], suf[N];

void dfs(ll x){
    if (x>=n){
        pw[x]=1;
        return;
    }
    pw[x]=v[x].size();
    for (ll i: v[x]){
        dfs(i);
        pw[x]=pw[x]*pw[i]%mod;
    }
}

void dfs2(ll x, ll now=1){
    if (x>=n){
        cnt[x-n+1]=ps[x-n+1]=now;
        return;
    }
    ll sz=v[x].size();
    pre[x].resize(sz);
    pre[x][0]=pw[v[x][0]];
    for (int i=1; i<sz; i++) pre[x][i]=pre[x][i-1]*pw[v[x][i]]%mod;
    suf[x].resize(sz);
    suf[x][sz-1]=pw[v[x][sz-1]];
    for (int i=sz-2; i>=0; i--) suf[x][i]=suf[x][i+1]*pw[v[x][i]]%mod;
    for (int i=0; i<sz; i++){
        ll tmp=now;
        if (i) tmp=tmp*pre[x][i-1]%mod;
        if (i<sz-1) tmp=tmp*suf[x][i+1]%mod;
        dfs2(v[x][i], tmp);
    }
}

void push(ll id, ll x, ll y){
    if (!lazy[id]) return;
    lazy[id]=0;
    seg[id]=((ps[y]-ps[x-1]-seg[id])%mod+mod)%mod;
    if (x!=y){
        lazy[id*2]^=1;
        lazy[id*2+1]^=1;
    }
}

void build(ll id=1, ll x=1, ll y=m){
    if (x==y){
        seg[id]=cnt[x]*a[x];
        lazy[id]=0;
        return;
    }
    ll mid=(x+y)/2;
    build(id*2, x, mid);
    build(id*2+1, mid+1, y);
    seg[id]=(seg[id*2]+seg[id*2+1])%mod;
}

void update(ll l, ll r, ll id=1, ll x=1, ll y=m){
    push(id, x, y);
    if (l<=x && y<=r){
        lazy[id]^=1;
        push(id, x, y);
        return;
    }
    if (l>y || r<x) return;
    ll mid=(x+y)/2;
    update(l, r, id*2, x, mid);
    update(l, r, id*2+1, mid+1, y);
    seg[id]=(seg[id*2]+seg[id*2+1])%mod;
}

ll qry(ll p, ll id=1, ll x=1, ll y=m){
    push(id, x, y);
    if (x==y) return seg[id];
    ll mid=(x+y)/2;
    if (p<=mid) return qry(p, id*2, x, mid);
    return qry(p, id*2+1, mid+1, y);
}

void init(int N, int M, vector<int> P, vector<int> A){
    n=N, m=M;
    for (int i=1; i<n+m; i++) v[P[i]].push_back(i);
    for (int i=0; i<m; i++) a[i+1]=A[i];
    dfs(0);
    dfs2(0);
    for (int i=2; i<=m; i++) ps[i]=(ps[i]+ps[i-1])%mod;
    build();
}

int count_ways(int L, int R){
    update(L-n+1, R-n+1);
    push(1, 1, m);
    return seg[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