oj.uz

Submission #788980

# Submission time Handle Problem Language Result Execution time Memory
788980 2023-07-20T19:03:15 Z mosiashvililuka Digital Circuit (IOI22_circuit) C++17
16 / 100
 851 ms 15768 KB 
#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,mod=1000002022LL,dp[200009],ALL[200009],f[200009],L,R,pr[200009],sf[200009],pas,N,seg[800009],seg2[800009],JM[200009],M,l,r,z,za;
vector <long long> v[200009];
void pushdown(long long q, long long w, long long rr){
    if(q!=w){
        seg2[rr*2]^=seg2[rr];
        seg2[rr*2+1]^=seg2[rr];
    }
    if(seg2[rr]!=0){
        seg2[rr]=0;
        seg[rr]=JM[w]-JM[q-1]-seg[rr]+mod*2;
        seg[rr]%=mod;
    }
}
void upd(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        seg2[rr]^=1;
        pushdown(q,w,rr);
        return;
    }
    upd(q,(q+w)/2,rr*2);
    upd((q+w)/2+1,w,rr*2+1);
    seg[rr]=seg[rr*2]+seg[rr*2+1];
    seg[rr]%=mod;
}
void read(long long q, long long w, long long rr){
    pushdown(q,w,rr);
    if(q>=l&&w<=r){
        z+=seg[rr];
        z%=mod;
        return;
    }
    read(q,(q+w)/2,rr*2);
    read((q+w)/2+1,w,rr*2+1);
}
void dfs(int q, int w){
    if(v[q].size()==0){
        ALL[q]=1;
        return;
    }
    ALL[q]=v[q].size();
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfs((*it),q);
        ALL[q]*=ALL[(*it)];ALL[q]%=mod;
    }

    long long qw=1;
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        pr[(*it)]=qw;
        qw*=ALL[(*it)];qw%=mod;
    }
    vector <long long>::iterator it=v[q].end();it--;
    qw=1;
    for( ; ; ){
        sf[(*it)]=qw;
        qw*=ALL[(*it)];qw%=mod;
        if(it==v[q].begin()) break;
        it--;
    }

}
void dfs2(int q, int w){
    dp[q]=dp[w];
    dp[q]*=pr[q];dp[q]%=mod;
    dp[q]*=sf[q];dp[q]%=mod;
    for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
        dfs2((*it),q);
    }
}
void init(int NN, int MM, std::vector<int> P, std::vector<int> A) {
    a=NN+MM;N=NN;M=MM;
    for(ii=1; ii<P.size(); ii++){
        i=ii+1;
        v[P[ii]+1].push_back(i);
    }

    for(i=N+1; i<=a; i++){
        f[i]=A[i-N-1];
    }
    dfs(1,0);
    pr[1]=sf[1]=1;
    dp[0]=1;
    dfs2(1,0);
    za=1;
    while(za<a-N) za*=2;

    for(i=N+1; i<=a; i++){
        JM[i-N]=dp[i];
    }
    for(i=1; i<=M; i++){
        JM[i]+=JM[i-1];JM[i]%=mod;
    }

    for(i=N+1; i<=a; i++){
        if(f[i]==0) continue;
        l=i-N;r=i-N;z=1;
        upd(1,za,1);
    }

    /*for(i=1; i<=a; i++){
        cout<<dp[i]<<" "<<pr[i]<<" "<<sf[i]<<"\n";
    }*/
}
int count_ways(int LL, int RR) {
    L=LL+1;R=RR+1;
    /*for(i=L; i<=R; i++) f[i]^=1;
    pas=0;
    for(i=N+1; i<=a; i++){
        if(f[i]==1){
            pas+=dp[i];pas%=mod;
        }
    }*/
    l=L-N;r=R-N;z=1;
    upd(1,za,1);
    l=1;r=a-N;z=0;
    read(1,za,1);
    pas=z;
    return pas;
}

Compilation message

circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:76:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(ii=1; ii<P.size(); ii++){
      |               ~~^~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Runtime error 8 ms 10240 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Runtime error 10 ms 10192 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Runtime error 8 ms 10240 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 10416 KB Output is correct
2 Correct 788 ms 15768 KB Output is correct
3 Correct 643 ms 15768 KB Output is correct
4 Correct 705 ms 15048 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 10416 KB Output is correct
2 Correct 788 ms 15768 KB Output is correct
3 Correct 643 ms 15768 KB Output is correct
4 Correct 705 ms 15048 KB Output is correct
5 Correct 573 ms 10312 KB Output is correct
6 Correct 810 ms 15748 KB Output is correct
7 Correct 718 ms 15732 KB Output is correct
8 Correct 851 ms 15752 KB Output is correct
9 Correct 381 ms 5328 KB Output is correct
10 Correct 687 ms 5716 KB Output is correct
11 Correct 781 ms 5712 KB Output is correct
12 Correct 749 ms 5712 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 3 ms 5032 KB Output is correct
3 Correct 2 ms 5072 KB Output is correct
4 Correct 3 ms 5072 KB Output is correct
5 Correct 3 ms 5072 KB Output is correct
6 Runtime error 10 ms 10192 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Runtime error 8 ms 10240 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Runtime error 8 ms 10240 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -