結果
問題 |
No.877 Range ReLU Query
|
ユーザー |
![]() |
提出日時 | 2019-09-06 22:41:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 1,950 bytes |
コンパイル時間 | 2,621 ms |
コンパイル使用メモリ | 201,736 KB |
最終ジャッジ日時 | 2025-01-07 16:54:16 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:47:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=] 47 | scanf("%lld", &a); | ~~~^ ~~ | | | | | int64_t* {aka long int*} | long long int* | %ld main.cpp:53:27: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=] 53 | scanf("%lld%lld%lld%lld", &com, &l, &r, &x); | ~~~^ ~~~~ | | | | long long int* int64_t* {aka long int*} | %ld main.cpp:53:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 3 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=] 53 | scanf("%lld%lld%lld%lld", &com, &l, &r, &x); | ~~~^ ~~ | | | | long long int* int64_t* {aka long int*} | %ld main.cpp:53:35: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=] 53 | scanf("%lld%lld%lld%lld", &com, &l, &r, &x); | ~~~^ ~~ | | | | long long int* int64_t* {aka long int*} | %ld main.cpp:53:39: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 5 has type ‘int64_
ソースコード
#include <bits/stdc++.h> /////////////////////////// // Range Sum Query (BIT) // /////////////////////////// class RSumQBIT { private: std::vector<int64_t> container_; int64_t getHelper(const int index) const { if (index < 0) return 0; if ((int)(container_.size()) <= index) return container_.back(); int64_t sum{}; for (int add_place{index}; add_place > 0; add_place -= add_place & -add_place) sum += container_[add_place]; return sum; } public: RSumQBIT(const int array_size) : container_(array_size + 1) {} // indexは0-indexed void update(const int index, const int64_t added) { for (int update_place{index + 1}; update_place < (int)(container_.size()); update_place += update_place & -update_place) container_[update_place] += added; } // left,rightは0-indexed、[left, right)の半開区間 int64_t get(const int left, const int right) const { return -getHelper(left) + getHelper(right); } }; int main() { int N, Q; scanf("%d%d", &N, &Q); std::vector<std::array<int64_t, 5>> queries(N + Q); // {1, l, r, x} // {2, index, a} for (int64_t i{}; i < N; i++) { int64_t a; scanf("%lld", &a); queries[i] = {2ll, i, i, a, i}; } for (int i{}; i < Q; i++) { int64_t com, l, r, x; scanf("%lld%lld%lld%lld", &com, &l, &r, &x); l--; queries[N + i] = {com, l, r, x, i}; } std::sort(queries.begin(), queries.end(), [](auto& a, auto& b) { return a[3] > b[3]; }); RSumQBIT sum(N), exist(N); std::vector<int64_t> ans(Q); for (auto& query: queries) { // for (int i{}; i < N; i++) // printf("%lld ", sum.get(i, i + 1)); // putchar('\n'); // for (int i{}; i < N; i++) // printf("%lld ", exist.get(i, i + 1)); // putchar('\n'); if (query[0] == 1) ans[query[4]] = sum.get(query[1], query[2]) - exist.get(query[1], query[2]) * query[3]; else { sum.update(query[1], query[3]); exist.update(query[1], 1); } } for (auto& e: ans) printf("%lld\n", e); return 0; }