oj.uz

Submission #790521

# Submission time Handle Problem Language Result Execution time Memory
790521 2023-07-22T19:13:48 Z borisAngelov Digital Circuit (IOI22_circuit) C++17
2 / 100
 511 ms 19792 KB 
#include "circuit.h"

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const long long mod = 1e9 + 2022;

int n, m;

vector<int> g[maxn];

long long contribution[maxn];

long long power(long long a, long long b)
{
    if (b == 0)
    {
        return 1LL;
    }

    if (b % 2 == 0)
    {
        long long result = power(a, b / 2);
        return (result * result) % mod;
    }

    return (a * power(a, b - 1)) % mod;
}

void dfs(int node, int dep)
{
    if (g[node].empty())
    {
        contribution[node] = power(2, n - dep);
        return;
    }

    for (int i = 0; i < g[node].size(); ++i)
    {
        dfs(g[node][i], dep + 1);
    }
}

long long preffix[maxn];

long long get_sum(int l, int r)
{
    if (l == 0)
    {
        return preffix[r];
    }

    return (preffix[r] - preffix[l - 1] + mod) % mod;
}

struct segment_tree
{
    struct vertex
    {
        long long sum;
        bool lazy;

        vertex()
        {
            sum = 0;
            lazy = false;
        }

        vertex(long long _sum, bool _lazy)
        {
            sum = _sum;
            lazy = _lazy;
        }
    };

    vertex tree[4 * maxn];

    void push_lazy(int node, int l, int r)
    {
        if (tree[node].lazy == true)
        {
            tree[node].sum = get_sum(l, r) - tree[node].sum;

            if (l != r)
            {
                tree[2 * node].lazy = 1 - tree[2 * node].lazy;
                tree[2 * node + 1].lazy = 1 - tree[2 * node + 1].lazy;
            }

            tree[node].lazy = false;
        }
    }

    void update(int node, int l, int r, int ql, int qr)
    {
        push_lazy(node, l, r);

        if (l > qr || r < ql)
        {
            return;
        }

        if (ql <= l && r <= qr)
        {
            tree[node].lazy = true;
            push_lazy(node, l, r);
            return;
        }

        int mid = (l + r) / 2;

        update(2 * node, l, mid, ql, qr);
        update(2 * node + 1, mid + 1, r, ql, qr);

        tree[node].sum = tree[2 * node].sum + tree[2 * node + 1].sum;
    }

    void update(int l, int r)
    {
        update(1, 0, m - 1, l, r);
    }
};

segment_tree tree;

void init(int N, int M, vector<int> P, vector<int> A)
{
    n = N;
    m = M;

    for (int i = 1; i < P.size(); ++i)
    {
        g[P[i]].push_back(i);
    }

    dfs(0, 0);

    for (int i = 0; i < m; ++i)
    {
        preffix[i] = contribution[i + n];

        if (i > 0)
        {
            preffix[i] += preffix[i - 1];
        }

        preffix[i] %= mod;
    }

    for (int i = 0; i < m; ++i)
    {
        if (A[i] == 1)
        {
            tree.update(i, i);
        }
    }
}

int count_ways(int L, int R)
{
    int l = L - n;
    int r = R - n;

    tree.update(l, r);

    return tree.tree[1].sum;
}

Compilation message

circuit.cpp: In function 'void dfs(int, int)':
circuit.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < g[node].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 1; i < P.size(); ++i)
      |                     ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17488 KB Output is correct
2 Correct 8 ms 17404 KB Output is correct
3 Correct 8 ms 17532 KB Output is correct
4 Correct 8 ms 17488 KB Output is correct
5 Correct 7 ms 17548 KB Output is correct
6 Correct 8 ms 17520 KB Output is correct
7 Correct 9 ms 17516 KB Output is correct
8 Correct 8 ms 17492 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17488 KB Output is correct
2 Incorrect 7 ms 17488 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17488 KB Output is correct
2 Correct 8 ms 17404 KB Output is correct
3 Correct 8 ms 17532 KB Output is correct
4 Correct 8 ms 17488 KB Output is correct
5 Correct 7 ms 17548 KB Output is correct
6 Correct 8 ms 17520 KB Output is correct
7 Correct 9 ms 17516 KB Output is correct
8 Correct 8 ms 17492 KB Output is correct
9 Correct 7 ms 17488 KB Output is correct
10 Incorrect 7 ms 17488 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 511 ms 19792 KB 1st lines differ - on the 1st token, expected: '431985922', found: '-747097920'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 511 ms 19792 KB 1st lines differ - on the 1st token, expected: '431985922', found: '-747097920'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 17488 KB Output is correct
2 Incorrect 7 ms 17488 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17488 KB Output is correct
2 Correct 8 ms 17404 KB Output is correct
3 Correct 8 ms 17532 KB Output is correct
4 Correct 8 ms 17488 KB Output is correct
5 Correct 7 ms 17548 KB Output is correct
6 Correct 8 ms 17520 KB Output is correct
7 Correct 9 ms 17516 KB Output is correct
8 Correct 8 ms 17492 KB Output is correct
9 Correct 7 ms 17488 KB Output is correct
10 Incorrect 7 ms 17488 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 17488 KB Output is correct
2 Correct 8 ms 17404 KB Output is correct
3 Correct 8 ms 17532 KB Output is correct
4 Correct 8 ms 17488 KB Output is correct
5 Correct 7 ms 17548 KB Output is correct
6 Correct 8 ms 17520 KB Output is correct
7 Correct 9 ms 17516 KB Output is correct
8 Correct 8 ms 17492 KB Output is correct
9 Correct 7 ms 17488 KB Output is correct
10 Incorrect 7 ms 17488 KB 1st lines differ - on the 1st token, expected: '52130940', found: '-1782334720'
11 Halted 0 ms 0 KB -