oj.uz

Submission #1057404

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

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

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

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 8 ms 34904 KB Output is correct
2 Execution timed out 3062 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 8 ms 35132 KB Output is correct
2 Correct 9 ms 35160 KB Output is correct
3 Correct 10 ms 35148 KB Output is correct
4 Correct 9 ms 35156 KB Output is correct
5 Correct 9 ms 35176 KB Output is correct
6 Correct 9 ms 35160 KB Output is correct
7 Correct 9 ms 35212 KB Output is correct
8 Correct 10 ms 35224 KB Output is correct
9 Correct 10 ms 35160 KB Output is correct
10 Correct 9 ms 35264 KB Output is correct
11 Correct 9 ms 35160 KB Output is correct
12 Correct 9 ms 35160 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 34904 KB Output is correct
2 Execution timed out 3062 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 407 ms 41304 KB Output is correct
2 Correct 586 ms 43608 KB Output is correct
3 Correct 573 ms 43608 KB Output is correct
4 Correct 564 ms 43608 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 41304 KB Output is correct
2 Correct 586 ms 43608 KB Output is correct
3 Correct 573 ms 43608 KB Output is correct
4 Correct 564 ms 43608 KB Output is correct
5 Correct 479 ms 41348 KB Output is correct
6 Correct 659 ms 43600 KB Output is correct
7 Correct 683 ms 43596 KB Output is correct
8 Correct 608 ms 43596 KB Output is correct
9 Correct 282 ms 35160 KB Output is correct
10 Correct 570 ms 35416 KB Output is correct
11 Correct 562 ms 35668 KB Output is correct
12 Correct 552 ms 35416 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35132 KB Output is correct
2 Correct 9 ms 35160 KB Output is correct
3 Correct 10 ms 35148 KB Output is correct
4 Correct 9 ms 35156 KB Output is correct
5 Correct 9 ms 35176 KB Output is correct
6 Correct 9 ms 35160 KB Output is correct
7 Correct 9 ms 35212 KB Output is correct
8 Correct 10 ms 35224 KB Output is correct
9 Correct 10 ms 35160 KB Output is correct
10 Correct 9 ms 35264 KB Output is correct
11 Correct 9 ms 35160 KB Output is correct
12 Correct 9 ms 35160 KB Output is correct
13 Correct 407 ms 41304 KB Output is correct
14 Correct 586 ms 43608 KB Output is correct
15 Correct 573 ms 43608 KB Output is correct
16 Correct 564 ms 43608 KB Output is correct
17 Correct 479 ms 41348 KB Output is correct
18 Correct 659 ms 43600 KB Output is correct
19 Correct 683 ms 43596 KB Output is correct
20 Correct 608 ms 43596 KB Output is correct
21 Correct 282 ms 35160 KB Output is correct
22 Correct 570 ms 35416 KB Output is correct
23 Correct 562 ms 35668 KB Output is correct
24 Correct 552 ms 35416 KB Output is correct
25 Correct 605 ms 45772 KB Output is correct
26 Correct 632 ms 45648 KB Output is correct
27 Correct 623 ms 45896 KB Output is correct
28 Correct 493 ms 45868 KB Output is correct
29 Correct 625 ms 52056 KB Output is correct
30 Correct 618 ms 52048 KB Output is correct

Subtask #7
0 / 28.0

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