oj.uz

Submission #710502

# Submission time Handle Problem Language Result Execution time Memory
710502 2023-03-15T09:45:25 Z ogibogi2004 Digital Circuit (IOI22_circuit) C++17
0 / 100
 674 ms 1436 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 674 ms 1436 KB 1st lines differ - on the 1st token, expected: '431985922', found: '795183922'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 674 ms 1436 KB 1st lines differ - on the 1st token, expected: '431985922', found: '795183922'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB 1st lines differ - on the 1st token, expected: '1', found: '2'
2 Halted 0 ms 0 KB -