Submission #1025070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025070		irmuun	Digital Circuit (IOI22_circuit)	C++17	Compilation error	0 ms	0 KiB

circuit

//Unfinished

#include<bits/stdc++.h>
//#include "circuit.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int mod=1e9+2022;

const int maxn=2e5;
vector<int>adj[maxn],dp(maxn,0);
vector<int>a;
int n,m;

array<int,3>merge(array<int,3>l,array<int,3>r){
    array<int,3>c;
    c[0]=(l[0]+r[0])%mod;
    c[1]=(l[1]+r[1])%mod;
    c[2]=0;
    return c;
}

struct segtree{
    int n;
    vector<array<int,3>>d;
    void init(int n){
        d.resize(4*n);
        build(1,0,n-1);
    }
    void build(int v,int l,int r){
        if(l==r){
            d[v][0]=dp[l];
            d[v][1]=0;
            d[v][2]=0;
            if(a[l]==1){
                swap(d[v][0],d[v][1]);
            }
            return;
        }
        int mid=(l+r)>>1;
        build(v*2,l,mid);
        build(v*2+1,mid+1,r);
        d[v]=merge(d[v*2],d[v*2+1]);
    }
    void update(int v,int l,int r,int L,int R){
        if(L>R) return;
        if(l==L&&r==R){
            swap(d[v][0],d[v][1]);
            d[v][2]^=1;
            return;
        }
        d[v][2]^=1;
        int cnt=d[v][2];
        int mid=(l+r)>>1;
        update(v*2,l,mid,L,min(R,mid));
        update(v*2+1,mid+1,r,max(L,mid+1),R);
        d[v]=merge(d[v*2],d[v*2+1]);
        d[v][2]=cnt;
        if(d[v][2]){
            swap(d[v][0],d[v][1]);
        }
    }
    int ans(){
        return d[1][1];
    }
};

segtree sg;

void init(int N,int M,vector<int>p,vector<int>A){
    n=N;
    m=M;
    a=A;
    for(int i=1;i<n+m;i++){
        adj[p[i]].pb(i);
    }
    fill(all(dp),1);
    queue<int>q;
    q.push(0);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y:adj[x]){
            dp[y]=1ll*dp[y]*dp[x]%mod*(int)adj[x].size()%mod;
            q.push(y);
        }
    }
    sg.init(m);
    for(int i=0;i<m;i++){
        cout<<dp[i+n]<<' ';
    }
    cout<<'\n';
}
 
int count_ways(int l,int r){
    sg.update(1,0,m-1,l-n,r-n);
    return sg.ans();
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N,M,Q;
    cin>>N>>M>>Q;
    vector<int>P(N+M),A(M);
    for(int i=0;i<N+M;i++){
        cin>>P[i];
    }
    for(int i=0;i<M;i++){
        cin>>A[i];
    }
    init(N,M,P,A);
    while(Q--){
        int L,R;
        cin>>L>>R;
        cout<<count_ways(L,R)<<"\n";
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccZF6xY8.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccut2Qc9.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status