oj.uz

Submission #1057390

# Submission time Handle Problem Language Result Execution time Memory
1057390 2024-08-13T18:38:44 Z sofijavelkovska Digital Circuit (IOI22_circuit) C++17
23 / 100
 3000 ms 23796 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 3092 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 2 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 3 ms 11352 KB Output is correct
5 Correct 3 ms 11352 KB Output is correct
6 Correct 3 ms 11608 KB Output is correct
7 Correct 4 ms 11608 KB Output is correct
8 Correct 4 ms 11608 KB Output is correct
9 Correct 3 ms 11608 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 11608 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 3092 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 384 ms 13656 KB Output is correct
2 Correct 571 ms 15696 KB Output is correct
3 Correct 559 ms 15908 KB Output is correct
4 Correct 560 ms 15704 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 13656 KB Output is correct
2 Correct 571 ms 15696 KB Output is correct
3 Correct 559 ms 15908 KB Output is correct
4 Correct 560 ms 15704 KB Output is correct
5 Correct 497 ms 13656 KB Output is correct
6 Correct 637 ms 15896 KB Output is correct
7 Correct 666 ms 15696 KB Output is correct
8 Correct 629 ms 15744 KB Output is correct
9 Correct 277 ms 11608 KB Output is correct
10 Correct 573 ms 11608 KB Output is correct
11 Correct 535 ms 11608 KB Output is correct
12 Correct 541 ms 11608 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 3 ms 11352 KB Output is correct
5 Correct 3 ms 11352 KB Output is correct
6 Correct 3 ms 11608 KB Output is correct
7 Correct 4 ms 11608 KB Output is correct
8 Correct 4 ms 11608 KB Output is correct
9 Correct 3 ms 11608 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 11608 KB Output is correct
13 Correct 384 ms 13656 KB Output is correct
14 Correct 571 ms 15696 KB Output is correct
15 Correct 559 ms 15908 KB Output is correct
16 Correct 560 ms 15704 KB Output is correct
17 Correct 497 ms 13656 KB Output is correct
18 Correct 637 ms 15896 KB Output is correct
19 Correct 666 ms 15696 KB Output is correct
20 Correct 629 ms 15744 KB Output is correct
21 Correct 277 ms 11608 KB Output is correct
22 Correct 573 ms 11608 KB Output is correct
23 Correct 535 ms 11608 KB Output is correct
24 Correct 541 ms 11608 KB Output is correct
25 Runtime error 27 ms 23796 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 3092 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 3092 ms 7256 KB Time limit exceeded
3 Halted 0 ms 0 KB -