#913175 (C++17) No.924 紲星

• 問題: No.924 紲星
• ユーザー: kuhaku
• 提出日時: 2023-09-13 16:37:11
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: TLE
• 実行時間: -
• コード長: 9,360 bytes
• コンパイル時間: 4,484 ms
• コンパイル使用メモリ: 247,792 KB
• 実行使用メモリ: 55,312 KB
• 最終ジャッジ日時: 2024-07-01 01:13:12
• 合計ジャッジ時間: 11,733 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 13,760 KB
testcase_01	AC	2 ms; 6,944 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	13 ms; 6,944 KB
testcase_04	AC	6 ms; 6,940 KB
testcase_05	AC	23 ms; 6,940 KB
testcase_06	AC	11 ms; 6,944 KB
testcase_07	AC	7 ms; 6,944 KB
testcase_08	TLE	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-

ソースコード

#line 1 "a.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/924"
#line 2 "/home/kuhaku/atcoder/github/algo/lib/template/template.hpp"
#pragma GCC target("sse4.2,avx2,bmi2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
template <class T, class U>
bool chmax(T &a, const U &b) {
    return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
bool chmin(T &a, const U &b) {
    return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr int MOD = 1000000007;
constexpr int MOD_N = 998244353;
constexpr double EPS = 1e-7;
constexpr double PI = M_PI;
#line 2 "/home/kuhaku/atcoder/github/algo/lib/algorithm/rollback_mo.hpp"

/**
 * @brief Mo's algorithm (rollback)
 * @see https://ei1333.hateblo.jp/entry/2017/09/11/211011
 * @see https://snuke.hatenablog.com/entry/2016/07/01/000000
 */
struct rollback_mo {
    rollback_mo(int n) : _left(), _right(), _order(), _size(n) {}

    void input(int q, int bias = 1, int closed = 0) {
        for (int i = 0; i < q; ++i) {
            int l, r;
            std::cin >> l >> r;
            this->add(l - bias, r - bias + closed);
        }
    }

    void add(int l, int r) {
        this->_left.emplace_back(l);
        this->_right.emplace_back(r);
    }
    void emplace(int l, int r) { return this->add(l, r); }
    void insert(int l, int r) { return this->add(l, r); }

    template <class F, class G, class H, class I>
    void solve(F rem, G save, H load, I add) {
        return solve(rem, save, load, add, add);
    }
    template <class F, class G, class H, class I, class J>
    void solve(F rem, G save, H load, I addl, J addr) {
        int q = this->_left.size();
        int width = std::max(1, int(this->_size / std::sqrt(q)));
        this->_order.resize(q);
        std::iota(this->_order.begin(), this->_order.end(), 0);
        std::sort(this->_order.begin(), this->_order.end(), [&](int a, int b) -> bool {
            if (this->_left[a] / width != this->_left[b] / width)
                return this->_left[a] < this->_left[b];
            return this->_right[a] < this->_right[b];
        });

        auto reset = save();
        for (auto idx : this->_order) {
            if (this->_right[idx] - this->_left[idx] < width) {
                for (int i = this->_left[idx]; i < this->_right[idx]; i++) addr(i);
                rem(idx);
                load(reset);
            }
        }

        int right = 0, last_block = -1;
        for (auto idx : this->_order) {
            if (this->_right[idx] - this->_left[idx] < width) continue;
            int block = this->_left[idx] / width;
            if (block != last_block) {
                load(reset);
                last_block = block;
                right = (block + 1) * width;
            }
            while (right < this->_right[idx]) addr(right++);
            auto snapshot = save();
            for (int j = (block + 1) * width - 1; j >= this->_left[idx]; --j) addl(j);
            rem(idx);
            load(snapshot);
        }
    }

  private:
    std::vector<int> _left, _right, _order;
    int _size;
};
#line 2 "/home/kuhaku/atcoder/github/algo/lib/data_structure/erasable_priority_queue.hpp"

/**
 * @brief 削除可能優先度付きキュー
 *
 * @tparam T
 */
template <class T, class Comp = std::less<>>
struct erasable_priority_queue {
    bool empty() const { return a.empty(); }
    int size() const { return a.size() - b.size(); }
    T top() const { return a.top(); }

    void insert(const T &x) { a.push(x); }
    void insert(T &&x) { a.push(std::move(x)); }
    void push(const T &x) { a.push(x); }
    void push(T &&x) { a.push(std::move(x)); }
    template <typename... Args>
    void emplace(Args &&...args) {
        a.emplace(std::forward<Args>(args)...);
    }

    void pop() { erase(a.top()); }

    void erase(T x) {
        b.emplace(x);
        while (!b.empty() && a.top() == b.top()) {
            a.pop(), b.pop();
        }
    }

  private:
    std::priority_queue<T, std::vector<T>, Comp> a, b;
};
#line 2 "/home/kuhaku/atcoder/github/algo/lib/math/undo_slope_trick.hpp"

/**
 * @brief slope trick
 *
 * @tparam T
 */
template <class T>
struct undo_slope_trick {
    undo_slope_trick() : min_f(), l(), r() {}

    T get_x() { return l.top(); }
    T get() { return min_f; }
    T get_y() { return get(); }

    /**
     * @brief Add f(x) = a
     *
     * @param a
     */
    void add(T a) {
        history.emplace(0, min_f);
        min_f += a;
    }

    /**
     * @brief Add f(x) = max(0, x - a)
     *
     * @param a
     */
    void add_f(T a) {
        if (!l.empty()) {
            history.emplace(0, min_f);
            min_f += std::max(T(), l.top() - a);
        }
        history.emplace(1, a);
        l.emplace(a);
        auto x = l.top();
        history.emplace(2, x);
        l.pop();
        history.emplace(3, x);
        r.emplace(x);
    }

    /**
     * @brief Add f(x) = max(0, a - x)
     *
     * @param a
     */
    void add_g(T a) {
        if (!r.empty()) {
            history.emplace(0, min_f);
            min_f += std::max(T(), a - r.top());
        }
        history.emplace(3, a);
        r.emplace(a);
        auto x = r.top();
        history.emplace(4, x);
        r.pop();
        history.emplace(1, x);
        l.emplace(x);
    }

    /**
     * @brief Add f(x) = abs(x - a) = max(0, x - a) + max(0, a - x)
     *
     * @param a
     */
    void add_abs(T a) {
        add_f(a);
        add_g(a);
    }

    void undo() {
        auto [x, y] = history.top();
        history.pop();
        if (x == 0) min_f = y;
        else if (x == 1) l.erase(y);
        else if (x == 2) l.emplace(y);
        else if (x == 3) r.erase(y);
        else r.emplace(y);
    }

    int snapshot() const { return history.size(); }

    void rollback(int x = 0) {
        while (x < (int)history.size()) undo();
    }

  private:
    T min_f;
    erasable_priority_queue<T> l;
    erasable_priority_queue<T, std::greater<>> r;
    std::stack<std::pair<int, T>> history;
};
#line 3 "/home/kuhaku/atcoder/github/algo/lib/template/macro.hpp"
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
#line 3 "/home/kuhaku/atcoder/github/algo/lib/template/sonic.hpp"
struct Sonic {
    Sonic() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }

    constexpr void operator()() const {}
} sonic;
#line 5 "/home/kuhaku/atcoder/github/algo/lib/template/atcoder.hpp"
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
    return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &i : v) is >> i;
    return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        os << (it == v.begin() ? "" : " ") << *it;
    }
    return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
    else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
    if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
    else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
template <typename T, typename... Args>
auto make_vector(T x, int arg, Args... args) {
    if constexpr (sizeof...(args) == 0) return std::vector<T>(arg, x);
    else return std::vector(arg, make_vector<T>(x, args...));
}
void setp(int n) {
    std::cout << std::fixed << std::setprecision(n);
}
void Yes(bool is_correct = true) {
    std::cout << (is_correct ? "Yes" : "No") << '\n';
}
void No(bool is_not_correct = true) {
    Yes(!is_not_correct);
}
void YES(bool is_correct = true) {
    std::cout << (is_correct ? "YES" : "NO") << '\n';
}
void NO(bool is_not_correct = true) {
    YES(!is_not_correct);
}
void Takahashi(bool is_correct = true) {
    std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n';
}
void Aoki(bool is_not_correct = true) {
    Takahashi(!is_not_correct);
}
#line 5 "a.cpp"

int main(void) {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    cin >> a;
    rollback_mo mo(n);
    vector<ll> ans(q);
    while (q--) {
        int l, r;
        cin >> l >> r;
        mo.add(l - 1, r);
    }

    undo_slope_trick<ll> st;
    auto rem = [&](int idx) {
        ans[idx] = st.get();
    };
    auto save = [&]() {
        return st.snapshot();
    };
    auto load = [&](int idx) {
        st.rollback(idx);
    };
    auto add = [&](int idx) {
        st.add_abs(a[idx]);
    };
    mo.solve(rem, save, load, add);
    for (auto x : ans) co(x);

    return 0;
}