Submission #1191215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191215		Amr	Digital Circuit (IOI22_circuit)	C++20	0 / 100	174 ms	2340 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;
ll siz = 1;
pair<ll,ll> seg[200005];
ll n;
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 + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
    seg[x].S = 2*seg[2*x+1].S*seg[2*x+2].S + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;

}
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);
        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 + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
    seg[x].S = 2*seg[2*x+1].S*seg[2*x+2].S + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    siz = M;
    a = A;
    n = N;
    build();
}

int count_ways(int L, int R) {
    upd(L,R+1);
    return seg[0].F;
  return 0;
}

• 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