제출 #790520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790520		borisAngelov	Digital Circuit (IOI22_circuit)	C++17	컴파일 에러	0 ms	0 KiB

circuit

#include "circuit.h"
#include "stub.cpp"

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

circuit.cpp: In function 'void dfs(int, int)':
circuit.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     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:134:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 1; i < P.size(); ++i)
      |                     ~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccN2BRQ5.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cccW4jI1.o:circuit.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status