Submission #650799

#	Time	Username	Problem	Language	Result	Execution time	Memory
650799		ShirleyM	Digital Circuit (IOI22_circuit)	C++17	16 / 100	1010 ms	11856 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;
const int mx_m = 1e5;

int n,m;
vi a;

struct node{
    int cnt0=0, cnt1=0;
    bool flag=0;

    node(int cnt0=0, int cnt1=0):cnt0(cnt0), cnt1(cnt1){}
};

node seg[4*mx_m];

void set_(int ind){
    swap(seg[ind].cnt0, seg[ind].cnt1);
    seg[ind].flag = !seg[ind].flag;
}

void push(int ind){
    if(seg[ind].flag){
        set_(2*ind);
        set_(2*ind+1);
        seg[ind].flag=0;
    }
}

void pull(int ind){
    seg[ind].cnt1 = ((seg[2*ind].cnt0 * seg[2*ind+1].cnt1) + (seg[2*ind].cnt1 * seg[2*ind+1].cnt0) + (2*seg[2*ind].cnt1*seg[2*ind+1].cnt1))%mod;
    seg[ind].cnt0 = ((seg[2*ind].cnt0 * seg[2*ind+1].cnt1) + (seg[2*ind].cnt1 * seg[2*ind+1].cnt0) + (2*seg[2*ind].cnt0*seg[2*ind+1].cnt0))%mod;
}

void build(int ind, int l, int r){
    if(l+1==r){
        int cnt0 = 0, cnt1=1;
        if(!a[l]) swap(cnt0, cnt1);
        seg[ind] = node(cnt0, cnt1);
        return;
    }
    int mid = (l+r)/2;
    build(2*ind, l, mid);
    build(2*ind+1, mid, r);
    pull(ind);
}

 void update_swap(int ind, int l, int r, int a, int b){
        if(a<=l && r<=b){
            set_(ind);
            return;
        }
        if(l>=b || r<=a) return;
        int mid = (l+r)/2;
        push(ind);
        update_swap(2*ind, l, mid, a,b);
        update_swap(2*ind+1, mid, r, a,b);
        pull(ind);
 }

 int query(){
     return seg[1].cnt1;
 }


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

int32_t count_ways(int32_t L, int32_t R) {
    int l=L, r=R;
    l-=n; r-=n;
    update_swap(1,0,m,l,r+1);
    return 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