Submission #944814

#	Time	Username	Problem	Language	Result	Execution time	Memory
944814		KG07	디지털 회로 (IOI22_circuit)	C++17	100 / 100	775 ms	37660 KiB

circuit

#include "circuit.h"

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

struct segment_tree{
    int n, m;
    long long tree_size[200002], sum[400004], counting[400004], multiplier[200002];
    bool toggle[400004];
    vector<int> child[100001], A;
    vector<long long> left_product[100001], right_product[100001];
    void init(int N, int M, vector<int> p, vector<int> a){
        n = N;
        m = M;
        A = a;
        tree_size[0] = 1LL;
        for(int i = 1; i < N+M; i++){
            tree_size[i] = 1LL;
            child[p[i]].push_back(i);
            left_product[p[i]].push_back(0LL);
            right_product[p[i]].push_back(0LL);
        }
    }
    void calculate_size(int N){
        if(N >= n)return;
        tree_size[N] = (long long) child[N].size();
        for(int i = 0; i < child[N].size(); i++){
            calculate_size(child[N][i]);
            left_product[N][i] = tree_size[child[N][i]];
            right_product[N][i] = tree_size[child[N][i]];
            tree_size[N] *= tree_size[child[N][i]];
            tree_size[N] %= 1000002022;
        }
        for(int i = 1; i < child[N].size(); i++){
            left_product[N][i] *= left_product[N][i-1];
            left_product[N][i] %= 1000002022;
        }
        for(int i = child[N].size()-1; i; i--){
            right_product[N][i-1] *= right_product[N][i];
            right_product[N][i-1] %= 1000002022;
        }
    }
    void calculate_multiplier(int N, long long M){
        if(N >= n){
            multiplier[N] = M;
            return;
        }
        if(child[N].size() == 1){
            calculate_multiplier(child[N][0], M);
            return;
        }
        for(int i = 0; i < child[N].size(); i++){
            if(!i)calculate_multiplier(child[N][i], (M*right_product[N][1])%1000002022);
            else if(i+1==child[N].size())calculate_multiplier(child[N][i], (M*left_product[N][child[N].size()-2])%1000002022);
            else calculate_multiplier(child[N][i], (M*((right_product[N][i+1]*left_product[N][i-1])%1000002022))%1000002022);
        }
    }
    void create_tree(int N, int l, int r){
        toggle[N] = false;
        if(l == r){
            sum[N] = multiplier[n+r-1];
            if(A[r-1])counting[N] = multiplier[n+r-1];
            else counting[N] = 0LL;
            return;
        }
        create_tree(2*N, l, (l+r)/2);
        create_tree(2*N+1,(l+r)/2+1, r);
        sum[N] = (sum[2*N] + sum[2*N+1]) % 1000002022;
        counting[N] = (counting[2*N] + counting[2*N+1]) % 1000002022;
    }
    void lazy_update(int N){
        if(toggle[N]){
            toggle[N] = false;
            toggle[2*N] = !toggle[2*N];
            toggle[2*N+1] = !toggle[2*N+1];
            counting[2*N] = (sum[2*N]-counting[2*N][phone]) % 1000002022;
            counting[2*N+1] = (sum[2*N+1]-counting[2*N+1][phone]) % 1000002022;
        }
    }
    void update(int N, int l, int r, int s, int t){
        if(l > t || r < s)return;
        if(l <= s && r >= t){
            toggle[N] = !toggle[N];
            counting[N] = (sum[N]-counting[N][phone]) % 1000002022;
            return;
        }
        lazy_update(N);
        update(2*N, l, r, s, (s+t)/2);
        update(2*N+1, l, r, (s+t)/2+1, t);
        counting[N] = (counting[2*N] + counting[2*N+1]) % 1000002022;
    }
} A;

void init(int N, int M, vector<int> p, vector<int> a) {
    A.init(N, M, p, a);
    A.calculate_size(0);
    A.calculate_multiplier(0, 1LL);
    A.create_tree(1, 1, M);
}

int count_ways(int L, int R) {
    A.update(1, L-A.n+1, R-A.n+1, 1, A.m);
    return A.counting[1];
}

Compilation message (stderr)

circuit.cpp: In member function 'void segment_tree::calculate_size(int)':
circuit.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int i = 0; i < child[N].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
circuit.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i = 1; i < child[N].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
circuit.cpp: In member function 'void segment_tree::calculate_multiplier(int, long long int)':
circuit.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0; i < child[N].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
circuit.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             else if(i+1==child[N].size())calculate_multiplier(child[N][i], (M*left_product[N][child[N].size()-2])%1000002022);
      |                     ~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 27 / 27
• Subtask 7: 28 / 28
• Subtask 8: 11 / 11