Submission #1191235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191235		Amr	Digital Circuit (IOI22_circuit)	C++20	0 / 100	206 ms	2592 KiB

circuit

#include "circuit.h"

#include <vector>
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
vector<int> a,p;
ll siz = 1;
pair<ll,ll> seg[2*200005];
ll n;
ll mod = 1000002022;
ll op[2*200005];
void build(ll x = 0, ll lx = 0, ll rx = siz)
{
    if(rx-lx==1)
    {
        seg[x].F = a[lx];
        seg[x].S = !a[lx];
        return;
    }
    ll mid = (lx+rx)/2;
    build(2*x+1,lx,mid);
    build(2*x+2,mid,rx);

    seg[x].F = ((2*seg[2*x+1].F*seg[2*x+2].F)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
    seg[x].S = ((2*seg[2*x+1].S*seg[2*x+2].S)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;

}
void upd(ll l , ll r, ll x = 0, ll lx = 0, ll rx = siz)
{
    if(lx>=r||rx<=l) return;
    if(lx>=l&&rx<=r)
    {
        swap(seg[x].F, seg[x].S);
        op[x] ^= 1;
        return;
    }
    ll mid = (lx+rx)/2;
    upd(l,r,2*x+1,lx,mid);
    upd(l,r,2*x+2,mid,rx);

    seg[x].F = ((2*seg[2*x+1].F*seg[2*x+2].F)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
    seg[x].S = ((2*seg[2*x+1].S*seg[2*x+2].S)%mod + (seg[2*x+1].S*seg[2*x+2].F)%mod + (seg[2*x+1].F*seg[2*x+2].S)%mod)%mod;
   // if(op[x]) swap(seg[x].F, seg[x].S);
}

void init(int N, int M, std::vector<int> P, std::vector<int> A) {
   p = P;
    siz = M;
    a = A;
    n = N;
    build();
}

int count_ways(int L, int R) {
    upd(L-n,R+-n);

    return seg[0].F;
}

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