Submission #710502

#	Time	Username	Problem	Language	Result	Execution time	Memory
710502		ogibogi2004	Digital Circuit (IOI22_circuit)	C++17	0 / 100	674 ms	1436 KiB

circuit

#include "circuit.h"

#include <vector>
#define ll long long
const int MAXN=1e5+6;
const ll mod=1000002022;
struct segment_tree
{
    int tree[4*MAXN];
    int lazy[4*MAXN];
    void push(int l,int r,int idx)
    {
        if(lazy[idx]==0)return;
        tree[idx]=(r-l+1)-tree[idx];
        if(l!=r)
        {
            lazy[idx*2]^=lazy[idx];
            lazy[idx*2+1]^=lazy[idx];
        }
        lazy[idx]=0;
    }
    void update(int idx,int l,int r,int ql,int qr)
    {
        push(l,r,idx);
        if(qr<l)return;
        if(ql>r)return;
        if(l>=ql&&r<=qr)
        {
            lazy[idx]^=1;
            push(l,r,idx);
            return;
        }
        int mid=(l+r)/2;
        update(idx*2,l,mid,ql,qr);
        update(idx*2+1,mid+1,r,ql,qr);
        tree[idx]=tree[idx*2]+tree[idx*2+1];
    }
    int query(int l,int r,int idx,int ql,int qr)
    {
        push(l,r,idx);
        if(l>qr)return 0;
        if(r<ql)return 0;
        if(l>=ql&&r<=qr)return tree[idx];
        int mid=(l+r)/2;
        return query(l,mid,idx*2,ql,qr)+query(mid+1,r,idx*2+1,ql,qr);
    }
}tr;
int m,n;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
    m=M;n=N;
    for(int i=1;i<=M;i++)
    {
        if(A[i-1])tr.update(1,1,M,i,i);
    }
}
ll fastpow(ll x,ll p)
{
    if(p==0)return 1;
    if(p==1)return x;
    ll t=fastpow(x,p/2);
    t*=t;t%=mod;
    if(p%2==1)
    {
        t*=x;
        t%=mod;
    }
    return t;
}
int count_ways(int L, int R) {
    tr.update(1,1,m,L-n+1,R-n+1);
    return fastpow(2,tr.query(1,m,1,1,m));
    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