結果
問題 | No.877 Range ReLU Query |
ユーザー | Haar |
提出日時 | 2020-05-07 06:07:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,967 bytes |
コンパイル時間 | 2,872 ms |
コンパイル使用メモリ | 226,432 KB |
実行使用メモリ | 106,092 KB |
最終ジャッジ日時 | 2023-09-16 07:42:15 |
合計ジャッジ時間 | 13,734 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | RE | - |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 4 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | AC | 670 ms
103,780 KB |
testcase_16 | AC | 629 ms
100,932 KB |
testcase_17 | AC | 655 ms
103,160 KB |
testcase_18 | AC | 661 ms
103,916 KB |
testcase_19 | AC | 396 ms
106,092 KB |
testcase_20 | AC | 486 ms
105,992 KB |
ソースコード
#include <bits/stdc++.h> #ifdef DEBUG #include <Mylib/Debug/debug.cpp> #else #define dump(...) #endif template <typename Monoid> class PersistentSegmentTree{ using value_type = typename Monoid::value_type; struct node{ value_type value; node *left = nullptr, *right = nullptr; node(const value_type &value): value(value){} }; int depth; node *root = nullptr; PersistentSegmentTree(int depth, node *root): depth(depth), root(root){} node* init(node *t, const std::vector<value_type> &init_list, int d, int &pos){ if(d == depth){ t = new node(pos < (int)init_list.size() ? init_list[pos] : Monoid::id()); ++pos; }else{ t = new node(Monoid::id()); t->left = init(t->left, init_list, d+1, pos); t->right = init(t->right, init_list, d+1, pos); t->value = Monoid::op(t->left->value, t->right->value); } return t; } public: PersistentSegmentTree(const std::vector<value_type> &init_list){ const int size = init_list.size(); depth = size == 1 ? 1 : 32 - __builtin_clz(size-1) + 1; int pos = 0; root = init(root, init_list, 1, pos); } PersistentSegmentTree(int size){ depth = size == 1 ? 1 : 32 - __builtin_clz(size-1) + 1; int pos = 0; root = init(root, std::vector<value_type>(size, Monoid::id()), 1, pos); } protected: node* update(node *t, int l, int r, int pos, const value_type &val) const { if(r <= pos or pos + 1 <= l){ return t; }else if(pos <= l and r <= pos + 1){ return new node(val); }else{ const int m = (l + r) >> 1; auto lp = update(t->left, l, m, pos, val); auto rp = update(t->right, m, r, pos, val); node *s = new node(Monoid::op(lp->value, rp->value)); s->left = lp; s->right = rp; return s; } } public: PersistentSegmentTree update(int i, const value_type &val) const { node *t = update(root, 0, 1 << (depth-1), i, val); return PersistentSegmentTree(depth, t); } protected: value_type get(node *t, int i, int j, int l, int r) const { if(i <= l and r <= j) return t->value; if(r <= i or j <= l) return Monoid::id(); const int m = (l + r) >> 1; return Monoid::op(get(t->left, i, j, l, m), get(t->right, i, j, m, r)); } public: value_type get(int i, int j) const { return get(root, i, j, 0, 1 << (depth-1)); } value_type at(int i) const { return get(i, i+1); } }; template <typename T> struct SumMonoid{ using value_type = T; constexpr inline static value_type id(){return 0;} constexpr inline static value_type op(const value_type &a, const value_type &b){return a + b;} }; template <typename M1, typename M2> struct PairMonoid{ using value_type = std::pair<typename M1::value_type, typename M2::value_type>; constexpr inline static value_type id(){ return {M1::id(), M2::id()}; } constexpr inline static value_type op(const value_type &a, const value_type &b){ return {M1::op(a.first, b.first), M2::op(a.second, b.second)}; } }; using M = SumMonoid<int64_t>; using Seg = PersistentSegmentTree<PairMonoid<M, M>>; int main(){ int N, Q; std::cin >> N >> Q; std::vector<int64_t> a(N); for(int i = 0; i < N; ++i) std::cin >> a[i]; std::vector<int64_t> l(Q), r(N), x(Q); for(int i = 0; i < Q; ++i){ int type; std::cin >> type >> l[i] >> r[i] >> x[i]; } std::vector<Seg> seg; seg.push_back(Seg(N)); { std::vector<std::pair<int64_t, int>> b(N); for(int i = 0; i < N; ++i) b[i] = std::make_pair(a[i], i); std::sort(b.rbegin(), b.rend()); for(auto [v, i] : b){ auto &s = seg.back(); seg.push_back(s.update(i, std::make_pair(v, 1))); } } std::sort(a.rbegin(), a.rend()); for(int i = 0; i < Q; ++i){ int j = a.rend() - std::lower_bound(a.rbegin(), a.rend(), x[i]); auto [v, c] = seg[j].get(l[i]-1, r[i]); auto ans = v - x[i] * c; std::cout << ans << "\n"; } return 0; }