oj.uz

Submission #1057411

# Submission time Handle Problem Language Result Execution time Memory
1057411 2024-08-13T18:54:40 Z sofijavelkovska Digital Circuit (IOI22_circuit) C++17
23 / 100
 3000 ms 23688 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;
    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 2 ms 11352 KB Output is correct
2 Execution timed out 3090 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 2 ms 11352 KB Output is correct
3 Correct 2 ms 11580 KB Output is correct
4 Correct 3 ms 11576 KB Output is correct
5 Correct 4 ms 11608 KB Output is correct
6 Correct 3 ms 11608 KB Output is correct
7 Correct 3 ms 11608 KB Output is correct
8 Correct 3 ms 11608 KB Output is correct
9 Correct 3 ms 11472 KB Output is correct
10 Correct 3 ms 11608 KB Output is correct
11 Correct 3 ms 11608 KB Output is correct
12 Correct 4 ms 11604 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11352 KB Output is correct
2 Execution timed out 3090 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 327 ms 13648 KB Output is correct
2 Correct 563 ms 15704 KB Output is correct
3 Correct 589 ms 15696 KB Output is correct
4 Correct 591 ms 15696 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 13648 KB Output is correct
2 Correct 563 ms 15704 KB Output is correct
3 Correct 589 ms 15696 KB Output is correct
4 Correct 591 ms 15696 KB Output is correct
5 Correct 494 ms 13656 KB Output is correct
6 Correct 608 ms 15696 KB Output is correct
7 Correct 574 ms 15696 KB Output is correct
8 Correct 618 ms 15896 KB Output is correct
9 Correct 284 ms 11608 KB Output is correct
10 Correct 505 ms 11608 KB Output is correct
11 Correct 601 ms 11608 KB Output is correct
12 Correct 536 ms 11608 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11352 KB Output is correct
2 Correct 2 ms 11352 KB Output is correct
3 Correct 2 ms 11580 KB Output is correct
4 Correct 3 ms 11576 KB Output is correct
5 Correct 4 ms 11608 KB Output is correct
6 Correct 3 ms 11608 KB Output is correct
7 Correct 3 ms 11608 KB Output is correct
8 Correct 3 ms 11608 KB Output is correct
9 Correct 3 ms 11472 KB Output is correct
10 Correct 3 ms 11608 KB Output is correct
11 Correct 3 ms 11608 KB Output is correct
12 Correct 4 ms 11604 KB Output is correct
13 Correct 327 ms 13648 KB Output is correct
14 Correct 563 ms 15704 KB Output is correct
15 Correct 589 ms 15696 KB Output is correct
16 Correct 591 ms 15696 KB Output is correct
17 Correct 494 ms 13656 KB Output is correct
18 Correct 608 ms 15696 KB Output is correct
19 Correct 574 ms 15696 KB Output is correct
20 Correct 618 ms 15896 KB Output is correct
21 Correct 284 ms 11608 KB Output is correct
22 Correct 505 ms 11608 KB Output is correct
23 Correct 601 ms 11608 KB Output is correct
24 Correct 536 ms 11608 KB Output is correct
25 Runtime error 29 ms 23688 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

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