oj.uz

Submission #1059472

# Submission time Handle Problem Language Result Execution time Memory
1059472 2024-08-15T02:59:32 Z shiomusubi496 Digital Circuit (IOI22_circuit) C++17
4 / 100
 581 ms 12984 KB 
#include "circuit.h"
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)

using namespace std;

using ll = long long;

template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }


constexpr ll MOD = 1000002022;

template<class A> class LazySegmentTree {
    using M = typename A::M;
    using E = typename A::E;
    using T = typename M::T;
    using U = typename E::T;

    int n, h;
    vector<T> dat;
    vector<U> laz;

    void all_apply(int k, U x) {
        dat[k] = A::op(x, dat[k]);
        if (k < n) laz[k] = E::op(laz[k], x);
    }

    void eval(int k) {
        if (laz[k] == E::id()) return;
        all_apply(k * 2, laz[k]);
        all_apply(k * 2 + 1, laz[k]);
    }

    void calc(int k) {
        dat[k] = M::op(dat[k * 2], dat[k * 2 + 1]);
    }

public:
    LazySegmentTree() = default;
    LazySegmentTree(int n_) {
        n = 1, h = 0;
        while (n < n_) n *= 2, ++h;
        dat.assign(2 * n, M::id());
        laz.assign(n, E::id());
    }
    LazySegmentTree(vector<T> v) {
        n = 1, h = 0;
        while (n < v.size()) n *= 2, ++h;
        dat.assign(2 * n, M::id());
        laz.assign(n, E::id());
        rep (i, v.size()) dat[n + i] = v[i];
        rrep2 (i, 1, n) calc(i);
    }
    void apply(int l, int r, U x) {
        l += n; r += n;
        rrep2 (i, 1, h + 1) {
            if (((l >> i) << i) != l) eval(l >> i);
            if (((r >> i) << i) != r) eval((r - 1) >> i);
        }
        for (int l2 = l, r2 = r; l2 < r2; l2 >>= 1, r2 >>= 1) {
            if (l2 & 1) all_apply(l2++, x);
            if (r2 & 1) all_apply(--r2, x);
        }
        rep2 (i, 1, h + 1) {
            if (((l >> i) << i) != l) calc(l >> i);
            if (((r >> i) << i) != r) calc((r - 1) >> i);
        }
    }
    T all_prod() const { return dat[1]; }
};

struct Act {
    struct M {
        using T = pair<ll, ll>;
        static T op(T a, T b) { return {(a.first + b.first) % MOD, (a.second + b.second) % MOD}; }
        static T id() { return {0, 0}; }
    };
    struct E {
        using T = bool;
        static T op(T a, T b) { return a ? !b : b; }
        static T id() { return false; }
    };
    static pair<ll, ll> op(bool f, pair<ll, ll> a) {
        if (!f) return a;
        return {a.second, a.first};
    }
};

int N, M;
vector<vector<int>> G;
vector<int> A;

vector<ll> coef;

LazySegmentTree<Act> seg;

void init(int N_, int M_, std::vector<int> P, std::vector<int> A_) {
    N = N_; M = M_;
    A = A_;
    G.assign(N + M, vector<int>());
    rep2 (i, 1, N + M) G[P[i]].push_back(i);
    vector<ll> B(N + M, 1);
    {
        auto dfs = [&](auto&& self, int v) -> void {
            if (v >= N) return;
            for (int c : G[v]) self(self, c);
            B[v] = G[v].size();
            for (int c : G[v]) (B[v] *= B[c]) %= MOD;
        };
        dfs(dfs, 0);
    }
    coef.assign(M, 0);
    auto dfs = [&](auto&& self, int v, ll p) -> void {
        if (v >= N) {
            coef[v - N] = p;
            return;
        }
        int n = G[v].size();
        vector<ll> cum1(n + 1, 1), cum2(n + 1, 1);
        rep (i, n) cum1[i + 1] = cum1[i] * B[G[v][i]] % MOD;
        rrep (i, n) cum2[i] = cum2[i + 1] * B[G[v][i]] % MOD;
        rep (i, n) self(self, G[v][i], p * (cum1[i] * cum2[i + 1] % MOD) % MOD);
    };
    dfs(dfs, 0, 1);

    vector<pair<ll, ll>> X(M);
    rep (i, M) {
        if (A[i] == 0) X[i] = {0, coef[i]};
        else X[i] = {coef[i], 0};
    }
    seg = LazySegmentTree<Act>(X);
}

int count_ways(int L, int R) {
    L = L - N;
    R = R + 1 - N;
    seg.apply(L, R, true);
    return seg.all_prod().first;
}

Compilation message

circuit.cpp: In instantiation of 'LazySegmentTree<A>::LazySegmentTree(std::vector<typename A::M::T>) [with A = Act; typename A::M::T = std::pair<long long int, long long int>]':
circuit.cpp:140:33:   required from here
circuit.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while (n < v.size()) n *= 2, ++h;
      |                ~~^~~~~~~~~~

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '489', found: '497'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB 4th lines differ - on the 1st token, expected: '872925214', found: '41993438'
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '489', found: '497'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 6744 KB Output is correct
2 Correct 543 ms 12984 KB Output is correct
3 Correct 581 ms 12888 KB Output is correct
4 Correct 562 ms 12848 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 6744 KB Output is correct
2 Correct 543 ms 12984 KB Output is correct
3 Correct 581 ms 12888 KB Output is correct
4 Correct 562 ms 12848 KB Output is correct
5 Incorrect 483 ms 6744 KB 3rd lines differ - on the 1st token, expected: '249436868', found: '280604666'
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Incorrect 0 ms 344 KB 4th lines differ - on the 1st token, expected: '872925214', found: '41993438'
6 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '489', found: '497'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 0 ms 344 KB 3rd lines differ - on the 1st token, expected: '489', found: '497'
4 Halted 0 ms 0 KB -