oj.uz

Submission #1057347

# Submission time Handle Problem Language Result Execution time Memory
1057347 2024-08-13T17:45:19 Z sofijavelkovska Digital Circuit (IOI22_circuit) C++17
18 / 100
 642 ms 15704 KB 
#include "circuit.h"
//#include "stub.cpp"

#include <bits/stdc++.h>
using namespace std;

const int MOD=1000002022, MAXN=(1<<17);

// maxn maxn

int n, m;
vector<int> parent, a;
vector<int> adj[MAXN];
int subtree[2*MAXN];
long long factor[2*MAXN];
long long ones[2*MAXN-1], zeros[2*MAXN-1];
int lazy[2*MAXN-1]={0};

long long power(long long n, long long k)
{
    long long result=1, mul=n;
    for (int i=0; i<32; i++)
    {
        if (k&(1<<i))
            result=result*mul%MOD;
        mul=mul*mul%MOD;
    }

    return result;
}

void calcsize(int x)
{
    if (x>=n)
        subtree[x]=0;
    else
        subtree[x]=1;
    for (auto y : adj[x])
    {
        calcsize(y);
        subtree[x]=subtree[x]+subtree[y];
    }

    return;
}

void calcfactor(int x, long long current)
{
    if (x!=0)
        current=current*power(2, subtree[x])%MOD;
    factor[x]=current;
    for (auto y : adj[x])
        calcfactor(y, current);

    return;
}

void propagate(int x, int l, int r)
{
    if (r-l==1)
    {
        lazy[x]=0;
        return;
    }
    if (lazy[x]==0)
        return;
    swap(ones[2*x+1], zeros[2*x+1]);
    swap(ones[2*x+2], zeros[2*x+2]);
    lazy[2*x+1]=(lazy[2*x+1]+1)%2;
    lazy[2*x+2]=(lazy[2*x+2]+1)%2;
    lazy[x]=0;

    return;
}

void update(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return;
    propagate(x, l, r);
    if (l>=lt && r<=rt)
    {
        swap(ones[x], zeros[x]);
        lazy[x]=(lazy[x]+1)%2;
        return;
    }
    update(2*x+1, l, (l+r)/2, lt, rt);
    update(2*x+2, (l+r)/2, r, lt, rt);
    ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
    zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;

    return;
}

void buildtree(int x, int l, int r)
{
    if (r-l==1)
    {
        if (l>=m)
        {
            ones[x]=0;
            zeros[x]=0;
            return;
        }
        if (a[l]==1)
        {
            ones[x]=factor[l+n];
            zeros[x]=0;
        }
        else
        {
            ones[x]=0;
            zeros[x]=factor[l+n];
        }
        return;
    }
    buildtree(2*x+1, l, (l+r)/2);
    buildtree(2*x+2, (l+r)/2, r);
    ones[x]=(ones[2*x+1]+ones[2*x+2])%MOD;
    zeros[x]=(zeros[2*x+1]+zeros[2*x+2])%MOD;

    return;
}

void init(int N, int M, vector<int> P, vector<int> A)
{
    n=N;
    m=M;
    parent=P;
    a=A;
    for (int i=1; i<n+m; i++)
        adj[parent[i]].push_back(i);
    calcsize(0);
    calcfactor(0, 1);
    buildtree(0, 0, MAXN);
    //for (int i=0; i<n+m; i++)
      //  cout << factor[i] << ' ';
    //cout << '\n';
    //cout << "root " << ones[0] << ' ' << zeros[0] << '\n';
    //for (int i=0; i<m; i++)
      //  cout << zeros[i+MAXN-1] << ' ' << ones[i+MAXN-1] << '\n';

    return;
}

int count_ways(int l, int r)
{
    l=l-n;
    r=r-n;
    update(0, 0, MAXN, l, r+1);
    //long long total=(ones[0]+MOD-zeros[0])%MOD;
    long long total=ones[0];

    return total;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 2 ms 11392 KB Output is correct
3 Correct 3 ms 11564 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Correct 3 ms 11352 KB Output is correct
7 Correct 4 ms 11352 KB Output is correct
8 Correct 3 ms 11352 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Incorrect 3 ms 11608 KB 1st lines differ - on the 1st token, expected: '706880838', found: '332918342'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 2 ms 11392 KB Output is correct
3 Correct 3 ms 11564 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Correct 3 ms 11352 KB Output is correct
7 Correct 4 ms 11352 KB Output is correct
8 Correct 3 ms 11352 KB Output is correct
9 Correct 2 ms 11352 KB Output is correct
10 Correct 3 ms 11352 KB Output is correct
11 Correct 2 ms 11352 KB Output is correct
12 Correct 3 ms 11352 KB Output is correct
13 Correct 2 ms 11352 KB Output is correct
14 Incorrect 3 ms 11608 KB 1st lines differ - on the 1st token, expected: '706880838', found: '332918342'
15 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 13752 KB Output is correct
2 Correct 604 ms 15696 KB Output is correct
3 Correct 568 ms 15696 KB Output is correct
4 Correct 543 ms 15704 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 13752 KB Output is correct
2 Correct 604 ms 15696 KB Output is correct
3 Correct 568 ms 15696 KB Output is correct
4 Correct 543 ms 15704 KB Output is correct
5 Correct 491 ms 13656 KB Output is correct
6 Correct 606 ms 15696 KB Output is correct
7 Correct 615 ms 15672 KB Output is correct
8 Correct 642 ms 15696 KB Output is correct
9 Correct 270 ms 11608 KB Output is correct
10 Correct 529 ms 11608 KB Output is correct
11 Correct 586 ms 11608 KB Output is correct
12 Correct 613 ms 11608 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 2 ms 11352 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Incorrect 3 ms 11608 KB 1st lines differ - on the 1st token, expected: '706880838', found: '332918342'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 2 ms 11392 KB Output is correct
3 Correct 3 ms 11564 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Correct 3 ms 11352 KB Output is correct
7 Correct 4 ms 11352 KB Output is correct
8 Correct 3 ms 11352 KB Output is correct
9 Correct 2 ms 11352 KB Output is correct
10 Correct 3 ms 11352 KB Output is correct
11 Correct 2 ms 11352 KB Output is correct
12 Correct 3 ms 11352 KB Output is correct
13 Correct 2 ms 11352 KB Output is correct
14 Incorrect 3 ms 11608 KB 1st lines differ - on the 1st token, expected: '706880838', found: '332918342'
15 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 2 ms 11392 KB Output is correct
3 Correct 3 ms 11564 KB Output is correct
4 Correct 3 ms 11352 KB Output is correct
5 Correct 2 ms 11352 KB Output is correct
6 Correct 3 ms 11352 KB Output is correct
7 Correct 4 ms 11352 KB Output is correct
8 Correct 3 ms 11352 KB Output is correct
9 Correct 2 ms 11352 KB Output is correct
10 Correct 3 ms 11352 KB Output is correct
11 Correct 2 ms 11352 KB Output is correct
12 Correct 3 ms 11352 KB Output is correct
13 Correct 2 ms 11352 KB Output is correct
14 Incorrect 3 ms 11608 KB 1st lines differ - on the 1st token, expected: '706880838', found: '332918342'
15 Halted 0 ms 0 KB -