oj.uz

Submission #1057418

# Submission time Handle Problem Language Result Execution time Memory
1057418 2024-08-13T18:59:14 Z sofijavelkovska Digital Circuit (IOI22_circuit) C++17
50 / 100
 3000 ms 24400 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[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;
        return;
    }
    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 11352 KB Output is correct
2 Execution timed out 3050 ms 7256 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 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11352 KB Output is correct
4 Correct 2 ms 11608 KB Output is correct
5 Correct 3 ms 11576 KB Output is correct
6 Correct 4 ms 11608 KB Output is correct
7 Correct 4 ms 11608 KB Output is correct
8 Correct 3 ms 11608 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 3 ms 11608 KB Output is correct
11 Correct 3 ms 11608 KB Output is correct
12 Correct 3 ms 11436 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 13656 KB Output is correct
2 Correct 533 ms 15704 KB Output is correct
3 Correct 593 ms 15696 KB Output is correct
4 Correct 572 ms 15696 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 13656 KB Output is correct
2 Correct 533 ms 15704 KB Output is correct
3 Correct 593 ms 15696 KB Output is correct
4 Correct 572 ms 15696 KB Output is correct
5 Correct 474 ms 13656 KB Output is correct
6 Correct 618 ms 15696 KB Output is correct
7 Correct 673 ms 15828 KB Output is correct
8 Correct 647 ms 15696 KB Output is correct
9 Correct 254 ms 11608 KB Output is correct
10 Correct 574 ms 11608 KB Output is correct
11 Correct 532 ms 11608 KB Output is correct
12 Correct 565 ms 11608 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 3 ms 11352 KB Output is correct
3 Correct 3 ms 11352 KB Output is correct
4 Correct 2 ms 11608 KB Output is correct
5 Correct 3 ms 11576 KB Output is correct
6 Correct 4 ms 11608 KB Output is correct
7 Correct 4 ms 11608 KB Output is correct
8 Correct 3 ms 11608 KB Output is correct
9 Correct 3 ms 11612 KB Output is correct
10 Correct 3 ms 11608 KB Output is correct
11 Correct 3 ms 11608 KB Output is correct
12 Correct 3 ms 11436 KB Output is correct
13 Correct 374 ms 13656 KB Output is correct
14 Correct 533 ms 15704 KB Output is correct
15 Correct 593 ms 15696 KB Output is correct
16 Correct 572 ms 15696 KB Output is correct
17 Correct 474 ms 13656 KB Output is correct
18 Correct 618 ms 15696 KB Output is correct
19 Correct 673 ms 15828 KB Output is correct
20 Correct 647 ms 15696 KB Output is correct
21 Correct 254 ms 11608 KB Output is correct
22 Correct 574 ms 11608 KB Output is correct
23 Correct 532 ms 11608 KB Output is correct
24 Correct 565 ms 11608 KB Output is correct
25 Correct 603 ms 17820 KB Output is correct
26 Correct 693 ms 18004 KB Output is correct
27 Correct 680 ms 18000 KB Output is correct
28 Correct 528 ms 18000 KB Output is correct
29 Correct 662 ms 24400 KB Output is correct
30 Correct 612 ms 24400 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Execution timed out 3050 ms 7256 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 11352 KB Output is correct
2 Execution timed out 3050 ms 7256 KB Time limit exceeded
3 Halted 0 ms 0 KB -