Submission #673312

#	Time	Username	Problem	Language	Result	Execution time	Memory
673312		Cyanmond	Progression (NOI20_progression)	C++17	100 / 100	2089 ms	77104 KiB

Progression

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1ll << 60;

template <class M>
class segtree {
    int n, seg_size;
    using T = typename M::T;
    std::vector<T> tree;

    void update(int i) {
        tree[i] = M::operate(tree[2 * i], tree[2 * i + 1]);
    }

  public:
    segtree(int n_) : n(n_) {
        seg_size = 1;
        while (seg_size < n) {
            seg_size *= 2;
        }
        tree.assign(2 * seg_size, M::identity());
    }

    void set(int i, T v) {
        i += seg_size;
        tree[i] = v;
        while (i != 1) {
            i /= 2;
            update(i);
        }
    }

    T fold(int l, int r) {
        T ret_l = M::identity(), ret_r = M::identity();
        for (l += seg_size, r += seg_size; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) {
                ret_l = M::operate(ret_l, tree[l++]);
            }
            if (r % 2 == 1) {
                ret_r = M::operate(tree[--r], ret_r);
            }
        }
        return M::operate(ret_l, ret_r);
    }

    T get(int i) {
        return tree[i + seg_size];
    }
};

template <class M>
class lazy_segtree {
    int n, seg_size, logn;
    using T = typename M::T;
    using E = typename M::E;
    std::vector<T> tree;
    std::vector<E> lazy;

    void update(int i) {
        tree[i] = M::operate(tree[2 * i], tree[2 * i + 1]);
    }

    void apply(int i, const E &v) {
        tree[i] = M::map(tree[i], v);
        if (i < seg_size) {
            lazy[i] = M::composite(lazy[i], v);
        }
    }

    void flush(int i) {
        apply(2 * i, lazy[i]);
        apply(2 * i + 1, lazy[i]);
        lazy[i] = M::e_identity();
    }

  public:
    lazy_segtree(int n_) : n(n_) {
        logn = 1;
        while ((1 << logn) < n) {
            ++logn;
        }
        seg_size = 1 << logn;
        tree.assign(2 * seg_size, M::t_identity());
        lazy.assign(seg_size, M::e_identity());
    }

    void assign(int i, const T &v) {
        i += seg_size;
        for (int d = logn; d >= 1; --d) {
            flush(i >> d);
        }
        tree[i] = v;
        for (int d = 1; d <= logn; ++d) {
            update(i >> d);
        }
    }

    void operate_range(int l, int r, const E &v) {
        l += seg_size;
        r += seg_size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) {
                flush(l >> d);
            }
            if (((r >> d) << d) != r) {
                flush((r - 1) >> d);
            }
        }

        for (int l2 = l, r2 = r; l2 < r2; l2 /= 2, r2 /= 2) {
            if (l2 % 2 == 1) {
                apply(l2++, v);
            }
            if (r2 % 2 == 1) {
                apply(--r2, v);
            }
        }

        for (int d = 1; d <= logn; ++d) {
            if (((l >> d) << d) != l) {
                update(l >> d);
            }
            if (((r >> d) << d) != r) {
                update((r - 1) >> d);
            }
        }
    }

    void operate_point(int i, const E &v) {
        operate_range(i, i + 1, v);
    }

    T fold(int l, int r) {
        l += seg_size;
        r += seg_size;
        for (int d = logn; d >= 1; --d) {
            if (((l >> d) << d) != l) {
                flush(l >> d);
            }
            if (((r >> d) << d) != r) {
                flush((r - 1) >> d);
            }
        }

        T ret_l = M::t_identity(), ret_r = M::t_identity();
        while (l < r) {
            if (l % 2 == 1) {
                ret_l = M::operate(ret_l, tree[l++]);
            }
            if (r % 2 == 1) {
                ret_r = M::operate(tree[--r], ret_r);
            }
            l /= 2;
            r /= 2;
        }
        return M::operate(ret_l, ret_r);
    }
};

struct M1 {
    // range sum
    struct T {
        i64 value;
        int width;
    };

    static T operate(T a, T b) {
        return {a.value + b.value, a.width + b.width};
    }

    static T t_identity() {
        return {0, 0};
    }

    struct E {
        i64 init;
        i64 add;
    };

    static T map(T a, E b) {
        if (b.init == inf) {
            return {a.value + a.width * b.add, a.width};
        } else {
            return {a.width * (b.init + b.add), a.width};
        }
    }

    static E composite(E a, E b) {
        if (b.init == inf) {
            return {a.init, a.add + b.add};
        } else {
            return b;
        }
    }

    static E e_identity() {
        return {inf, 0};
    }
};

struct M2 {
    // on off max
    struct T {
        int l;
        int r;
        int ma;
        int width;
    };

    static T operate(T l, T r) {
        if (l.width == -1) {
            return r;
        }
        if (r.width == -1) {
            return l;
        }
        T ret;
        ret.width = l.width + r.width;
        ret.l = l.l;
        ret.r = r.r;
        if (l.l == l.width) {
            ret.l = l.l + r.l;
        }
        if (r.r == r.width) {
            ret.r = l.r + r.r;
        }
        ret.ma = std::max({ret.l, ret.r, l.ma, r.ma, l.r + r.l});
        return ret;
    }

    static T identity() {
        return {0, 0, 0, -1};
    }
};

int main() {
    int N, Q;
    std::cin >> N >> Q;
    std::vector<i64> D(N);
    for (auto &e : D) {
        std::cin >> e;
    }
    std::vector<int> T(Q), L(Q), R(Q);
    std::vector<i64> S(Q), C(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> T[i] >> L[i] >> R[i];
        --L[i];
        if (T[i] == 1 or T[i] == 2) {
            std::cin >> S[i] >> C[i];
        }
    }

    // diff of diff
    std::vector<i64> diffs(N - 1);
    for (int i = 1; i < N; ++i) {
        diffs[i - 1] = D[i] - D[i - 1];
    }
    diffs.insert(diffs.begin(), D[0]);

    lazy_segtree<M1> seg(N);
    for (int i = 0; i < N; ++i) {
        seg.assign(i, {diffs[i], 1});
    }

    auto access = [&](const int i) {
        return seg.fold(0, i + 1).value;
    };

    segtree<M2> oz(N - 2);
    std::set<int> zeros;
    for (int i = 2; i < N; ++i) {
        if (D[i] - D[i - 1] == D[i - 1] - D[i - 2]) {
            oz.set(i - 2, {1, 1, 1, 1});
        } else {
            oz.set(i - 2, {0, 0, 0, 1});
            zeros.insert(i - 2);
        }
    }

    auto update = [&](int i) {
        if (i >= N - 2 or i < 0) {
            return;
        }
        const auto a = access(i), b = access(i + 1), c = access(i + 2);
        if (b - a == c - b) {
            if (oz.get(i).ma == 1) {
                return;
            }
            oz.set(i, {1, 1, 1, 1});
            zeros.erase(i);
        } else {
            if (oz.get(i).ma == 0) {
                return;
            }
            oz.set(i, {0, 0, 0, 1});
            zeros.insert(i);
        }
    };

    auto range_set_one = [&](int l, int r) {
        // [l, r - 2)
        auto itr = zeros.lower_bound(l);
        while (itr != zeros.end()) {
            if (*itr >= r - 2) {
                break;
            }
            oz.set(*itr, {1, 1, 1, 1});
            itr = zeros.erase(itr);
        }  
    };

    for (int q = 0; q < Q; ++q) {
        if (T[q] == 1) {
            seg.operate_point(L[q], {inf, S[q]});
            seg.operate_range(L[q] + 1, R[q], {inf, C[q]});
            if (R[q] != N) {
                seg.operate_point(R[q], {inf, -(S[q] + (R[q] - L[q] - 1) * C[q])});
            }
            update(L[q] - 2);
            update(L[q] - 1);
            update(R[q] - 2);
            update(R[q] - 1);
        }
        if (T[q] == 2) {
            const auto lt = R[q] == N ? 0 : access(R[q]);
            const auto fa = access(L[q] - 1);
            seg.operate_point(L[q], {S[q] - fa, 0});
            seg.operate_range(L[q] + 1, R[q], {C[q], 0});
            if (R[q] != N) {
                seg.operate_point(R[q], {lt - (S[q] + (R[q] - L[q] - 1) * C[q]), 0});
            }
            update(L[q] - 2);
            update(L[q] - 1);
            update(R[q] - 2);
            update(R[q] - 1);
            range_set_one(L[q], R[q]);
        }

        if (T[q] == 3) {
            if (R[q] - L[q] <= 2) {
                std::cout << R[q] - L[q] << std::endl;
                continue;
            }
            const auto res = oz.fold(L[q], R[q] - 2).ma;
            std::cout << res + 2 << std::endl;
        }        
    }
}

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17