oj.uz

Submission #777436

# Submission time Handle Problem Language Result Execution time Memory
777436 2023-07-09T09:02:32 Z alexander707070 Digital Circuit (IOI22_circuit) C++17
52 / 100
 1002 ms 32584 KB 
#include<bits/stdc++.h>
#define MAXN 800007
using namespace std;

const long long mod=1000002022;

int n,m,maxdep,pw;
long long st[MAXN],total,diff,zeros,ans,a[MAXN];
long long pref[MAXN];
vector<int> v[MAXN];

long long power(long long x,int y){
    if(y==0)return 1;
    if(y==1)return x;
    if(y==2)return (x*x)%mod;
    if(y%2==0)return power(power(x,y/2),2);
    return (power(power(x,y/2),2)*x)%mod;
}

void dfs2(int x,int dep){
    if(v[x].empty()){
        st[x]=power(2,n-dep);
        return;
    }

    for(int i=0;i<v[x].size();i++){
        dfs2(v[x][i],dep+1);
    }
}

int tree[MAXN],lazy[MAXN];

int sum(int l,int r){
    if(l==0)return pref[r];
    return (pref[r]-pref[l-1]+mod)%mod;
}

void psh(int v,int l,int r){
    if(lazy[v]==0)return;
    int tt=(l+r)/2;

    tree[2*v]=(sum(l,tt)-tree[2*v]+mod)%mod;
    lazy[2*v]^=1; 
    
    tree[2*v+1]=(sum(tt+1,r)-tree[2*v+1]+mod)%mod;
    lazy[2*v+1]^=1;

    lazy[v]=0;
}

void update(int v,int l,int r,int ll,int rr){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v]=(sum(l,r)-tree[v]+mod)%mod;
        lazy[v]^=1;
    }else{
        int tt=(l+r)/2;
        psh(v,l,r);

        update(2*v,l,tt,ll,min(tt,rr));
        update(2*v+1,tt+1,r,max(tt+1,ll),rr);

        tree[v]=(tree[2*v]+tree[2*v+1])%mod;
    }
}

void init(int N, int M,vector<int> P,vector<int> A){
    n=N; m=M;

    for(int i=1;i<N+M;i++){
        v[P[i]].push_back(i);
    }    

    dfs2(0,0);
    for(int i=0;i<m;i++){
        pref[i]=st[i+N];
        if(i>0)pref[i]+=pref[i-1];
        pref[i]%=mod;
    }

    for(int i=0;i<m;i++){
        if(A[i]==1)update(1,0,m-1,i,i);
    }
}

int count_ways(int L, int R){
    L-=n; R-=n;
    update(1,0,m-1,L,R);

    return tree[1];
}

/*
int main(){
    init(7, 8, {-1, 0, 0,1,1,2,2,3,3,4,4,5,5,6,6}, {0,0,0,0,0,0,0,0});
    cout<<count_ways(7,14)<<"\n";
}
*/

Compilation message

circuit.cpp: In function 'void dfs2(int, int)':
circuit.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19016 KB Output is correct
2 Correct 10 ms 19024 KB Output is correct
3 Correct 10 ms 19168 KB Output is correct
4 Correct 10 ms 19172 KB Output is correct
5 Correct 10 ms 19152 KB Output is correct
6 Correct 10 ms 19152 KB Output is correct
7 Correct 10 ms 19152 KB Output is correct
8 Correct 10 ms 19152 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Correct 11 ms 19024 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 10 ms 19152 KB Output is correct
5 Correct 10 ms 19152 KB Output is correct
6 Correct 10 ms 19152 KB Output is correct
7 Correct 10 ms 19152 KB Output is correct
8 Correct 10 ms 19192 KB Output is correct
9 Correct 10 ms 19152 KB Output is correct
10 Correct 10 ms 19152 KB Output is correct
11 Correct 10 ms 19152 KB Output is correct
12 Correct 10 ms 19152 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19016 KB Output is correct
2 Correct 10 ms 19024 KB Output is correct
3 Correct 10 ms 19168 KB Output is correct
4 Correct 10 ms 19172 KB Output is correct
5 Correct 10 ms 19152 KB Output is correct
6 Correct 10 ms 19152 KB Output is correct
7 Correct 10 ms 19152 KB Output is correct
8 Correct 10 ms 19152 KB Output is correct
9 Correct 9 ms 19024 KB Output is correct
10 Correct 11 ms 19024 KB Output is correct
11 Correct 10 ms 19036 KB Output is correct
12 Correct 10 ms 19152 KB Output is correct
13 Correct 10 ms 19152 KB Output is correct
14 Correct 10 ms 19152 KB Output is correct
15 Correct 10 ms 19152 KB Output is correct
16 Correct 10 ms 19192 KB Output is correct
17 Correct 10 ms 19152 KB Output is correct
18 Correct 10 ms 19152 KB Output is correct
19 Correct 10 ms 19152 KB Output is correct
20 Correct 10 ms 19152 KB Output is correct
21 Incorrect 10 ms 19152 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 21752 KB Output is correct
2 Correct 660 ms 24492 KB Output is correct
3 Correct 711 ms 24620 KB Output is correct
4 Correct 664 ms 23752 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 21752 KB Output is correct
2 Correct 660 ms 24492 KB Output is correct
3 Correct 711 ms 24620 KB Output is correct
4 Correct 664 ms 23752 KB Output is correct
5 Correct 680 ms 21772 KB Output is correct
6 Correct 863 ms 24476 KB Output is correct
7 Correct 780 ms 24396 KB Output is correct
8 Correct 901 ms 24468 KB Output is correct
9 Correct 404 ms 19280 KB Output is correct
10 Correct 889 ms 19392 KB Output is correct
11 Correct 795 ms 19408 KB Output is correct
12 Correct 701 ms 19408 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 19024 KB Output is correct
2 Correct 11 ms 19024 KB Output is correct
3 Correct 10 ms 19036 KB Output is correct
4 Correct 10 ms 19152 KB Output is correct
5 Correct 10 ms 19152 KB Output is correct
6 Correct 10 ms 19152 KB Output is correct
7 Correct 10 ms 19152 KB Output is correct
8 Correct 10 ms 19192 KB Output is correct
9 Correct 10 ms 19152 KB Output is correct
10 Correct 10 ms 19152 KB Output is correct
11 Correct 10 ms 19152 KB Output is correct
12 Correct 10 ms 19152 KB Output is correct
13 Correct 574 ms 21752 KB Output is correct
14 Correct 660 ms 24492 KB Output is correct
15 Correct 711 ms 24620 KB Output is correct
16 Correct 664 ms 23752 KB Output is correct
17 Correct 680 ms 21772 KB Output is correct
18 Correct 863 ms 24476 KB Output is correct
19 Correct 780 ms 24396 KB Output is correct
20 Correct 901 ms 24468 KB Output is correct
21 Correct 404 ms 19280 KB Output is correct
22 Correct 889 ms 19392 KB Output is correct
23 Correct 795 ms 19408 KB Output is correct
24 Correct 701 ms 19408 KB Output is correct
25 Correct 680 ms 27792 KB Output is correct
26 Correct 933 ms 27832 KB Output is correct
27 Correct 1002 ms 28036 KB Output is correct
28 Correct 744 ms 27960 KB Output is correct
29 Correct 775 ms 32584 KB Output is correct
30 Correct 728 ms 32560 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19016 KB Output is correct
2 Correct 10 ms 19024 KB Output is correct
3 Correct 10 ms 19168 KB Output is correct
4 Correct 10 ms 19172 KB Output is correct
5 Correct 10 ms 19152 KB Output is correct
6 Correct 10 ms 19152 KB Output is correct
7 Correct 10 ms 19152 KB Output is correct
8 Correct 10 ms 19152 KB Output is correct
9 Correct 9 ms 19024 KB Output is correct
10 Correct 11 ms 19024 KB Output is correct
11 Correct 10 ms 19036 KB Output is correct
12 Correct 10 ms 19152 KB Output is correct
13 Correct 10 ms 19152 KB Output is correct
14 Correct 10 ms 19152 KB Output is correct
15 Correct 10 ms 19152 KB Output is correct
16 Correct 10 ms 19192 KB Output is correct
17 Correct 10 ms 19152 KB Output is correct
18 Correct 10 ms 19152 KB Output is correct
19 Correct 10 ms 19152 KB Output is correct
20 Correct 10 ms 19152 KB Output is correct
21 Incorrect 10 ms 19152 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19016 KB Output is correct
2 Correct 10 ms 19024 KB Output is correct
3 Correct 10 ms 19168 KB Output is correct
4 Correct 10 ms 19172 KB Output is correct
5 Correct 10 ms 19152 KB Output is correct
6 Correct 10 ms 19152 KB Output is correct
7 Correct 10 ms 19152 KB Output is correct
8 Correct 10 ms 19152 KB Output is correct
9 Correct 9 ms 19024 KB Output is correct
10 Correct 11 ms 19024 KB Output is correct
11 Correct 10 ms 19036 KB Output is correct
12 Correct 10 ms 19152 KB Output is correct
13 Correct 10 ms 19152 KB Output is correct
14 Correct 10 ms 19152 KB Output is correct
15 Correct 10 ms 19152 KB Output is correct
16 Correct 10 ms 19192 KB Output is correct
17 Correct 10 ms 19152 KB Output is correct
18 Correct 10 ms 19152 KB Output is correct
19 Correct 10 ms 19152 KB Output is correct
20 Correct 10 ms 19152 KB Output is correct
21 Incorrect 10 ms 19152 KB 1st lines differ - on the 1st token, expected: '759476520', found: '833967706'
22 Halted 0 ms 0 KB -