oj.uz

Submission #1057410

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

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

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

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>=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 5 ms 20568 KB Output is correct
2 Execution timed out 3095 ms 12376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Execution timed out 3095 ms 12376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 24920 KB Output is correct
2 Correct 577 ms 26960 KB Output is correct
3 Correct 624 ms 26960 KB Output is correct
4 Correct 566 ms 26968 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 24920 KB Output is correct
2 Correct 577 ms 26960 KB Output is correct
3 Correct 624 ms 26960 KB Output is correct
4 Correct 566 ms 26968 KB Output is correct
5 Correct 537 ms 24920 KB Output is correct
6 Correct 620 ms 26960 KB Output is correct
7 Correct 627 ms 26960 KB Output is correct
8 Correct 628 ms 27184 KB Output is correct
9 Correct 262 ms 20824 KB Output is correct
10 Correct 487 ms 20824 KB Output is correct
11 Correct 563 ms 20824 KB Output is correct
12 Correct 575 ms 20824 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Correct 4 ms 20568 KB Output is correct
3 Correct 6 ms 20824 KB Output is correct
4 Correct 6 ms 20824 KB Output is correct
5 Correct 5 ms 20824 KB Output is correct
6 Correct 5 ms 20824 KB Output is correct
7 Correct 5 ms 20824 KB Output is correct
8 Correct 5 ms 20824 KB Output is correct
9 Correct 6 ms 20824 KB Output is correct
10 Correct 5 ms 20824 KB Output is correct
11 Correct 5 ms 20824 KB Output is correct
12 Correct 5 ms 20824 KB Output is correct
13 Correct 406 ms 24920 KB Output is correct
14 Correct 577 ms 26960 KB Output is correct
15 Correct 624 ms 26960 KB Output is correct
16 Correct 566 ms 26968 KB Output is correct
17 Correct 537 ms 24920 KB Output is correct
18 Correct 620 ms 26960 KB Output is correct
19 Correct 627 ms 26960 KB Output is correct
20 Correct 628 ms 27184 KB Output is correct
21 Correct 262 ms 20824 KB Output is correct
22 Correct 487 ms 20824 KB Output is correct
23 Correct 563 ms 20824 KB Output is correct
24 Correct 575 ms 20824 KB Output is correct
25 Correct 641 ms 29260 KB Output is correct
26 Correct 646 ms 29264 KB Output is correct
27 Correct 620 ms 29456 KB Output is correct
28 Correct 521 ms 29264 KB Output is correct
29 Correct 665 ms 35712 KB Output is correct
30 Correct 600 ms 35664 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Execution timed out 3095 ms 12376 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20568 KB Output is correct
2 Execution timed out 3095 ms 12376 KB Time limit exceeded
3 Halted 0 ms 0 KB -