oj.uz

Submission #1057417

# Submission time Handle Problem Language Result Execution time Memory
1057417 2024-08-13T18:58:33 Z sofijavelkovska Digital Circuit (IOI22_circuit) C++17
50 / 100
 3000 ms 27472 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[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>=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 4 ms 14424 KB Output is correct
2 Execution timed out 3087 ms 10328 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 14424 KB Output is correct
2 Correct 3 ms 14600 KB Output is correct
3 Correct 5 ms 14680 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 4 ms 14656 KB Output is correct
6 Correct 5 ms 14680 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 4 ms 14680 KB Output is correct
11 Correct 4 ms 14680 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Execution timed out 3087 ms 10328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16728 KB Output is correct
2 Correct 525 ms 18968 KB Output is correct
3 Correct 475 ms 18776 KB Output is correct
4 Correct 551 ms 18748 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 16728 KB Output is correct
2 Correct 525 ms 18968 KB Output is correct
3 Correct 475 ms 18776 KB Output is correct
4 Correct 551 ms 18748 KB Output is correct
5 Correct 397 ms 16656 KB Output is correct
6 Correct 562 ms 18740 KB Output is correct
7 Correct 560 ms 18984 KB Output is correct
8 Correct 498 ms 18920 KB Output is correct
9 Correct 217 ms 14680 KB Output is correct
10 Correct 421 ms 14680 KB Output is correct
11 Correct 496 ms 14680 KB Output is correct
12 Correct 484 ms 14680 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Correct 3 ms 14600 KB Output is correct
3 Correct 5 ms 14680 KB Output is correct
4 Correct 4 ms 14680 KB Output is correct
5 Correct 4 ms 14656 KB Output is correct
6 Correct 5 ms 14680 KB Output is correct
7 Correct 3 ms 14680 KB Output is correct
8 Correct 3 ms 14680 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 4 ms 14680 KB Output is correct
11 Correct 4 ms 14680 KB Output is correct
12 Correct 3 ms 14680 KB Output is correct
13 Correct 324 ms 16728 KB Output is correct
14 Correct 525 ms 18968 KB Output is correct
15 Correct 475 ms 18776 KB Output is correct
16 Correct 551 ms 18748 KB Output is correct
17 Correct 397 ms 16656 KB Output is correct
18 Correct 562 ms 18740 KB Output is correct
19 Correct 560 ms 18984 KB Output is correct
20 Correct 498 ms 18920 KB Output is correct
21 Correct 217 ms 14680 KB Output is correct
22 Correct 421 ms 14680 KB Output is correct
23 Correct 496 ms 14680 KB Output is correct
24 Correct 484 ms 14680 KB Output is correct
25 Correct 518 ms 21020 KB Output is correct
26 Correct 568 ms 21148 KB Output is correct
27 Correct 592 ms 21128 KB Output is correct
28 Correct 504 ms 21072 KB Output is correct
29 Correct 627 ms 27400 KB Output is correct
30 Correct 584 ms 27472 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Execution timed out 3087 ms 10328 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14424 KB Output is correct
2 Execution timed out 3087 ms 10328 KB Time limit exceeded
3 Halted 0 ms 0 KB -