結果

問題 No.2065 Sum of Min
ユーザー kyo1
提出日時 2022-09-02 22:12:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 155 ms / 2,000 ms
コード長 3,090 bytes
コンパイル時間 2,286 ms
コンパイル使用メモリ 210,896 KB
最終ジャッジ日時 2025-02-07 01:22:11
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
template <typename T, typename F>
class SegmentTree {
public:
SegmentTree(const std::size_t size, const T identity, const F operate)
: identity(identity),
operate(operate),
nodes((1 << (32 - __builtin_clz(size))) << 1, identity) {}
SegmentTree(const std::vector<T> &values, const T identity, const F operate)
: identity(identity),
operate(operate),
nodes((1 << (32 - __builtin_clz(values.size()))) << 1, identity) {
std::copy(values.begin(), values.end(), nodes.begin() + size());
for (std::size_t i = size() - 1; i > 0; i--) {
nodes[i] = operate(nodes[i << 1], nodes[(i << 1) | 1]);
}
}
std::size_t size() const { return nodes.size() >> 1; }
void update(const std::size_t index, const T value) {
assert(index < size());
nodes[index + size()] = value;
for (std::size_t i = (index + size()) >> 1; i > 0; i >>= 1) {
nodes[i] = operate(nodes[i << 1], nodes[(i << 1) | 1]);
}
}
T fold(const std::size_t left, const std::size_t right) const { // [left, right)
assert(left < right && right <= size());
T x = identity;
T y = identity;
for (std::size_t l = left + size(), r = right + size(); l < r; l >>= 1, r >>= 1) {
if (l % 2 != 0) x = operate(x, nodes[l++]);
if (r % 2 != 0) y = operate(nodes[--r], y);
}
return operate(x, y);
}
private:
const T identity;
const F operate;
std::vector<T> nodes;
};
template <typename T, typename F>
SegmentTree<T, F> make_segment_tree(const std::size_t size, const T identity, const F operate) {
return SegmentTree<T, F>(size, identity, operate);
}
template <typename T, typename F>
SegmentTree<T, F> make_segment_tree(const std::vector<T> &values, const T identity,
const F operate) {
return SegmentTree<T, F>(values, identity, operate);
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N, Q;
cin >> N >> Q;
vector<int64_t> A(N);
for (auto &&e : A) {
cin >> e;
}
vector<tuple<int64_t, int, int>> XLR(Q);
for (auto &&[x, l, r] : XLR) {
cin >> l >> r >> x;
l--;
}
vector<int> indices(Q);
iota(indices.begin(), indices.end(), 0);
sort(indices.begin(), indices.end(), [&XLR](const auto a, const auto b) {
const auto [ax, al, ar] = XLR[a];
const auto [bx, bl, br] = XLR[b];
return ax > bx;
});
priority_queue<pair<int64_t, int>> que;
for (int i = 0; i < N; i++) {
que.emplace(A[i], i);
}
auto st1 = make_segment_tree<int64_t>(A, 0, [](const auto a, const auto b) { return a + b; });
auto st2 = make_segment_tree<int64_t>(N, 0, [](const auto a, const auto b) { return a + b; });
vector<int64_t> res(Q);
for (const int i : indices) {
const auto [x, l, r] = XLR[i];
while (!que.empty() && x < que.top().first) {
st1.update(que.top().second, 0);
st2.update(que.top().second, 1);
que.pop();
}
res[i] = st1.fold(l, r) + x * st2.fold(l, r);
}
for (const auto &e : res) {
cout << e << '\n';
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0