oj.uz

Submission #1057403

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

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

const long long MOD=1000002022, MAXN=(1<<19);

long long n, m;
vector<int> parent, a;
vector<long long> adj[MAXN];
long long subtree[2*MAXN];
long long factor[2*MAXN];
long long ones[2*MAXN-1], zeros[2*MAXN-1];
long long lazy[2*MAXN-1]={0};

long long power(long long n, long long k)
{
    long long result=1, mul=n;
    for (long long i=0; i<32; i++)
    {
        if (k&(1<<i))
            result=result*mul%MOD;
        mul=mul*mul%MOD;
    }

    return result;
}

void calcsize(long long 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(long long x, long long current)
{
    if (x>=n)
        return;
    long long l=adj[x][0];
    long long 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(long long x, long long l, long long 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(long long x, long long l, long long r, long long lt, long long 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(long long x, long long l, long long 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 9 ms 35160 KB Output is correct
2 Execution timed out 3084 ms 18520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35160 KB Output is correct
2 Execution timed out 3084 ms 18520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 41328 KB Output is correct
2 Correct 620 ms 43600 KB Output is correct
3 Correct 570 ms 43596 KB Output is correct
4 Correct 621 ms 43600 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 41328 KB Output is correct
2 Correct 620 ms 43600 KB Output is correct
3 Correct 570 ms 43596 KB Output is correct
4 Correct 621 ms 43600 KB Output is correct
5 Correct 469 ms 41616 KB Output is correct
6 Correct 678 ms 43928 KB Output is correct
7 Correct 602 ms 43924 KB Output is correct
8 Correct 599 ms 43608 KB Output is correct
9 Correct 281 ms 35160 KB Output is correct
10 Correct 578 ms 35412 KB Output is correct
11 Correct 555 ms 35672 KB Output is correct
12 Correct 586 ms 35416 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35160 KB Output is correct
2 Correct 8 ms 35160 KB Output is correct
3 Correct 9 ms 35172 KB Output is correct
4 Correct 9 ms 35160 KB Output is correct
5 Correct 9 ms 35160 KB Output is correct
6 Correct 8 ms 35160 KB Output is correct
7 Correct 8 ms 35160 KB Output is correct
8 Correct 10 ms 35212 KB Output is correct
9 Correct 9 ms 35160 KB Output is correct
10 Correct 8 ms 35160 KB Output is correct
11 Correct 8 ms 35160 KB Output is correct
12 Correct 8 ms 35164 KB Output is correct
13 Correct 390 ms 41328 KB Output is correct
14 Correct 620 ms 43600 KB Output is correct
15 Correct 570 ms 43596 KB Output is correct
16 Correct 621 ms 43600 KB Output is correct
17 Correct 469 ms 41616 KB Output is correct
18 Correct 678 ms 43928 KB Output is correct
19 Correct 602 ms 43924 KB Output is correct
20 Correct 599 ms 43608 KB Output is correct
21 Correct 281 ms 35160 KB Output is correct
22 Correct 578 ms 35412 KB Output is correct
23 Correct 555 ms 35672 KB Output is correct
24 Correct 586 ms 35416 KB Output is correct
25 Correct 662 ms 46212 KB Output is correct
26 Correct 653 ms 46332 KB Output is correct
27 Correct 644 ms 46340 KB Output is correct
28 Correct 508 ms 45648 KB Output is correct
29 Correct 659 ms 52664 KB Output is correct
30 Correct 627 ms 52016 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35160 KB Output is correct
2 Execution timed out 3084 ms 18520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35160 KB Output is correct
2 Execution timed out 3084 ms 18520 KB Time limit exceeded
3 Halted 0 ms 0 KB -