結果
| 問題 | No.877 Range ReLU Query |
| ユーザー |
 niuez
|
| 提出日時 | 2019-09-07 17:00:13 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,655 bytes |
| コンパイル時間 | 2,156 ms |
| コンパイル使用メモリ | 187,024 KB |
| 実行使用メモリ | 27,384 KB |
| 最終ジャッジ日時 | 2024-11-08 10:17:04 |
| 合計ジャッジ時間 | 8,884 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | RE | - |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
ソースコード
#include <memory>
// for test
#include <vector>
namespace niu {
/*
*
* ---- Persistent Segment Tree ----
*
* Persistent Segment Tree can do the following persisted operation.
* - accumulate the elements in any range of array in time O(logN)
* - update the value of element in time O(logN)
*
* ====> template argments <====
*
* + Monoid
* - static Monoid::operation(Monoid, Monoid) -> Monoid
* - static Monoid::identity() -> Monoid
*
* ====> member types <====
*
* + size_type | std::size_t
* + value_type | Monoid
*
* ====> member functions <====
*
* * N = the number of elements
*
* + update(const size_type idx, value_type val)
* - change the value of the idx-th elements to "val"
* - return the new updated persistent segment tree.
* - in time O(logN)
* + accumulate(size_type left, size_type right)
* - accumulate the elements in [left, right)
* - in time O(logN)
*
*/
template<class Monoid>
class persistent_segment_tree {
public:
using value_type = Monoid;
using size_type = std::size_t;
protected:
class node {
public:
using node_type = std::shared_ptr<node>;
value_type data;
node_type left;
node_type right;
public:
node(value_type data): data(std::move(data)), left(), right() {}
node(value_type data, node_type left, node_type right):
data(std::move(data)), left(std::move(left)), right(std::move(right)) {}
};
using node_type = std::shared_ptr<node>;
node_type root;
size_type N;
static node_type build(size_type l, size_type r) {
if(l + 1 >= r) {
return node_type(new node(value_type::identity()));
}
else {
return node_type(new node(
value_type::identity(),
build(l, (l + r) >> 1),
build((l + r) >> 1, r)
));
}
}
static node_type update(const node_type& node, size_type i, value_type val, size_type l, size_type r) {
if(i == l && i + 1 == r) return node_type(new class node(std::move(val)));
else if(l <= i && i < ((l + r) >> 1)) {
node_type left = update(node->left, i, std::move(val), l, (l + r) >> 1);
node_type right = node->right;
return node_type(new class node(
value_type::operation(left->data, right->data),
std::move(left),
std::move(right)
));
}
else {
node_type left = node->left;
node_type right = update(node->right, i, std::move(val), (l + r) >> 1, r);
return node_type(new class node(
value_type::operation(left->data, right->data),
std::move(left),
std::move(right)
));
}
}
static value_type accumulate(const node_type& node, size_type a, size_type b, size_type l, size_type r) {
if(b <= l || r <= a) return value_type::identity();
else if(a <= l && r <= b) return node->data;
else return value_type::operation(
accumulate(node->left, a, b, l, (l + r) / 2),
accumulate(node->right, a, b, (l + r) / 2, r)
);
}
persistent_segment_tree(node_type root, size_type n): root(root), N(n) {}
public:
persistent_segment_tree(): root() {}
persistent_segment_tree(size_type n): root(build(0, n)), N(n) {}
persistent_segment_tree(const persistent_segment_tree& tree): root(tree.root), N(tree.N) {}
persistent_segment_tree(persistent_segment_tree&& tree): root(std::move(tree.root)), N(tree.N) {}
persistent_segment_tree& operator=(const persistent_segment_tree& tree) {
root = tree.root;
N = tree.N;
return *this;
}
persistent_segment_tree& operator=(persistent_segment_tree&& tree) {
root = std::move(tree.root);
N = tree.N;
return *this;
}
persistent_segment_tree update(size_type idx, value_type val) const {
return persistent_segment_tree(update(root, idx, std::move(val), 0, N), N);
}
value_type accumulate(size_type left, size_type right) {
return accumulate(root, left, right, 0, N);
}
};
}
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const
struct sm {
long long x, y;
sm(long long a, long long b): x(a), y(b) {}
static sm identity() { return sm(0, 0); }
static sm operation(sm a, sm b) { return sm(a.x + b.x, a.y + b.y); }
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
i64 n, q;
cin >> n >> q;
vector<i64> a(n);
vector<pair<i64, i64>> vec;
vector<pair<i64, i64>> vec2;
rep(i,0,n) cin >> a[i];
rep(i,0,n) vec.push_back({ a[i], i });
niu::persistent_segment_tree<sm> seg(n);
rep(i,0,n) vec2.push_back({ a[i], 1 });
rep(i,0,n) seg = seg.update(i, {a[i], 1});
sort(all(vec));
i64 ii = 0;
vector<pair<pair<i64,i64>, pair<i64, i64>>> query;
rep(i,0,q) {
i64 com, l, r, x;
cin >> com >> l >> r >> x;
query.push_back({ {x, i}, { l, r } });
}
vector<i64> ans(q);
sort(all(query));
for(auto qq: query) {
i64 l = qq.second.first;
i64 r = qq.second.second;
i64 x = qq.first.first;
i64 ai = qq.first.second;
while(ii < vec.size() && vec[ii].first - x <= 0) {
i64 i = vec[ii].second;
seg = seg.update(i,{0, 0});
ii++;
}
auto res = seg.accumulate(l - 1, r);
ans[ai] = res.x - res.y * x;
}
rep(i,0,q) {
cout << ans[i] << endl;
}
}