Submission #1238629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238629		MarwenElarbi	Digital Circuit (IOI22_circuit)	C++17	16 / 100	302 ms	4260 KiB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=4e5+5;
const int MOD = 1e9 + 2022 ;
int a[nax];
long long dp[2][nax];
bool lazy[nax];
int n,m;
void merge(int pos){
    dp[0][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[0][pos*2+1]*dp[0][pos*2+2]*2;
    dp[1][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[1][pos*2+1]*dp[1][pos*2+2]*2;
    dp[0][pos]%=MOD;
    dp[1][pos]%=MOD;
}
void build(int pos,int l,int r){
    if(l==r){
        dp[a[l]][pos]=1;
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    merge(pos);
}
void expand(int pos){
    if(lazy[pos]){
        swap(dp[0][pos*2+1],dp[1][pos*2+1]);
        swap(dp[0][pos*2+2],dp[1][pos*2+2]);
        lazy[pos*2+1]^=1;
        lazy[pos*2+2]^=1;
    }
    lazy[pos]=0;
}
void update(int pos,int l,int r,int left,int right){
    if(l>r||r<left||l>right) return;
    if(left<=l&&r<=right){
        lazy[pos]^=1;
        swap(dp[0][pos],dp[1][pos]);
        return;
    }
    expand(pos);
    int mid=(r+l)/2;
    update(pos*2+1,l,mid,left,right);
    update(pos*2+2,mid+1,r,left,right);
    merge(pos);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A){
    n=N;m=M;
    for (int i = 0; i < M; ++i) a[i]=A[i];
    build(0,0,m-1);
}

int count_ways(int L, int R) {
    L-=n;R-=n;
    update(0,0,m-1,L,R);
    return dp[1][0];
}

• 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