oj.uz

Submission #1057413

# Submission time Handle Problem Language Result Execution time Memory
1057413 2024-08-13T18:56:57 Z sofijavelkovska Digital Circuit (IOI22_circuit) C++17
50 / 100
 3000 ms 30592 KB 
#include "circuit.h"
//#include "stub.cpp"

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

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

int n, m;
vector<int> parent, a;
vector<int> adj[2*MAXN];
int subtree[4*MAXN];
long long factor[4*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>=n)
        return;
    int l=adj[x][0];
    int r=adj[x][1];
    factor[l]=current*power(2, subtree[r])%MOD;
    factor[r]=current*power(2, subtree[l])%MOD;
    calcfactor(l, factor[l]);
    calcfactor(r, factor[r]);

    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;
    if (l>=lt && r<=rt)
    {
        swap(ones[x], zeros[x]);
        lazy[x]=(lazy[x]+1)%2;
        return;
    }
    propagate(x, l, r);
    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);

    return;
}

int count_ways(int l, int r)
{
    l=l-n;
    r=r-n;
    update(0, 0, MAXN, l, r+1);

    return ones[0];
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Execution timed out 3094 ms 11352 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Correct 3 ms 15448 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 3 ms 15704 KB Output is correct
5 Correct 3 ms 15704 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 3 ms 15712 KB Output is correct
8 Correct 4 ms 15704 KB Output is correct
9 Correct 3 ms 15704 KB Output is correct
10 Correct 3 ms 15704 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 3 ms 15704 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Execution timed out 3094 ms 11352 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 17752 KB Output is correct
2 Correct 588 ms 19792 KB Output is correct
3 Correct 570 ms 19768 KB Output is correct
4 Correct 539 ms 19800 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 17752 KB Output is correct
2 Correct 588 ms 19792 KB Output is correct
3 Correct 570 ms 19768 KB Output is correct
4 Correct 539 ms 19800 KB Output is correct
5 Correct 458 ms 17752 KB Output is correct
6 Correct 619 ms 19792 KB Output is correct
7 Correct 622 ms 19800 KB Output is correct
8 Correct 609 ms 19800 KB Output is correct
9 Correct 309 ms 15704 KB Output is correct
10 Correct 610 ms 15704 KB Output is correct
11 Correct 608 ms 15704 KB Output is correct
12 Correct 579 ms 15704 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Correct 3 ms 15448 KB Output is correct
3 Correct 4 ms 15704 KB Output is correct
4 Correct 3 ms 15704 KB Output is correct
5 Correct 3 ms 15704 KB Output is correct
6 Correct 3 ms 15704 KB Output is correct
7 Correct 3 ms 15712 KB Output is correct
8 Correct 4 ms 15704 KB Output is correct
9 Correct 3 ms 15704 KB Output is correct
10 Correct 3 ms 15704 KB Output is correct
11 Correct 3 ms 15704 KB Output is correct
12 Correct 3 ms 15704 KB Output is correct
13 Correct 427 ms 17752 KB Output is correct
14 Correct 588 ms 19792 KB Output is correct
15 Correct 570 ms 19768 KB Output is correct
16 Correct 539 ms 19800 KB Output is correct
17 Correct 458 ms 17752 KB Output is correct
18 Correct 619 ms 19792 KB Output is correct
19 Correct 622 ms 19800 KB Output is correct
20 Correct 609 ms 19800 KB Output is correct
21 Correct 309 ms 15704 KB Output is correct
22 Correct 610 ms 15704 KB Output is correct
23 Correct 608 ms 15704 KB Output is correct
24 Correct 579 ms 15704 KB Output is correct
25 Correct 604 ms 24212 KB Output is correct
26 Correct 619 ms 24144 KB Output is correct
27 Correct 632 ms 24164 KB Output is correct
28 Correct 524 ms 24152 KB Output is correct
29 Correct 674 ms 30544 KB Output is correct
30 Correct 634 ms 30592 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Execution timed out 3094 ms 11352 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15448 KB Output is correct
2 Execution timed out 3094 ms 11352 KB Time limit exceeded
3 Halted 0 ms 0 KB -