Submission #650801

#	Time	Username	Problem	Language	Result	Execution time	Memory
650801		ShirleyM	Digital Circuit (IOI22_circuit)	C++17	16 / 100	1051 ms	18252 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()

const int mod = 1000002022;

int n,m;
vvi adj;
vi a;
//vi cnt_st, cnt_h;
vi mul;

struct seg{
    int l,r,mid;
    int cnt0=0, cnt1=0;
    seg *lp, *rp;
    bool flag=0;

    void init(int l_, int r_){
        l=l_; r=r_;
        mid = (l+r)/2;
        if(l+1 < r){
            lp = new seg();
            rp = new seg();
            lp->init(l,mid);
            rp->init(mid,r);
        }
    }

    void set(){
        int tmp = cnt0;
        cnt0 = cnt1;
        cnt1 = tmp;
        flag=!flag;
    }

    void push(){
        if(flag){
            lp->set();
            rp->set();
            flag=0;
        }
    }

    void pull(){
        cnt1 = ((lp->cnt0 * rp->cnt1)%mod + (lp->cnt1 * rp->cnt0)%mod + (2*lp->cnt1*rp->cnt1)%mod)%mod;
        cnt0 = ((lp->cnt0 * rp->cnt1)%mod + (lp->cnt1 * rp->cnt0)%mod + (2*lp->cnt0*rp->cnt0)%mod)%mod;
    }

    void update_swap(int a, int b){
        if(a<=l && r<=b){
            set();
            return;
        }
        if(l>=b || r<=a) return;
        push();
        lp->update_swap(a,b);
        rp->update_swap(a,b);
        pull();
    }

    void update(int ind, int val){
        if(l==r-1){
            if(val){
                cnt1=1; cnt0=0;
            }
            else{
                cnt0=1; cnt1=0;
            }
            return;
        }
        if(ind<mid) lp->update(ind,val);
        else rp->update(ind,val);
        pull();
    }

    int query(){
        return cnt1;
    }
};

seg sg;

void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
    n=N;m=M;
    adj.resize(n+m);
    loop(i,1,n+m){
        adj[P[i]].pb(i);
    }
    a.resize(n+m);
    sg.init(0,m);
    loop(i,0,m){
        sg.update(i,A[i]);
        a[i+n] = A[i];
    }
}

int32_t count_ways(int32_t L, int32_t R) {
    int l=L, r=R;
    l-=n; r-=n;
    sg.update_swap(l,r+1);
    return sg.query();

}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11