結果
問題 | No.1000 Point Add and Array Add |
ユーザー | rsk0315 |
提出日時 | 2020-02-28 22:59:35 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 3,429 bytes |
コンパイル時間 | 635 ms |
コンパイル使用メモリ | 58,368 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-04-21 20:11:54 |
合計ジャッジ時間 | 4,092 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 4 ms
5,376 KB |
testcase_16 | AC | 104 ms
8,704 KB |
testcase_17 | AC | 85 ms
6,400 KB |
testcase_18 | AC | 141 ms
9,728 KB |
testcase_19 | AC | 142 ms
9,472 KB |
testcase_20 | AC | 132 ms
9,600 KB |
testcase_21 | AC | 137 ms
9,728 KB |
testcase_22 | AC | 137 ms
9,600 KB |
testcase_23 | AC | 138 ms
9,728 KB |
ソースコード
#include <climits> #include <vector> #include <utility> template < typename Monoid, typename Container = std::vector<typename Monoid::first_type> > class dual_segment_tree { public: using size_type = size_t; using first_type = typename Monoid::first_type; using second_type = typename Monoid::second_type; using value_type = first_type; using binary_operation = typename Monoid::binary_operation; using external_binary_operation = typename Monoid::external_binary_operation; using container = Container; private: size_type M_base_size; binary_operation M_op1; external_binary_operation M_op2; container M_c; public: dual_segment_tree() = default; dual_segment_tree(dual_segment_tree const&) = default; dual_segment_tree(dual_segment_tree&&) = default; dual_segment_tree(size_type n): M_base_size(n), M_op1(binary_operation()), M_op2(external_binary_operation()), M_c(n+n, M_op1.identity) {} dual_segment_tree(size_type n, first_type const& x): M_base_size(n), M_op1(binary_operation()), M_op2(external_binary_operation()), M_c(n+n, M_op1.identity) { modify(0, n, x); } template <typename InputIt> dual_segment_tree(InputIt first, InputIt last): M_base_size(std::distance(first, last)), M_op1(binary_operation()), M_op2(external_binary_operation()), M_c(M_base_size*2) { for (size_type i = M_base_size; first != last; ++i) M_c[i] = *first++; } dual_segment_tree& operator =(dual_segment_tree const&) = default; dual_segment_tree& operator =(dual_segment_tree&&) = default; void modify(size_type l, size_type r, second_type const& x) { l += M_base_size; r += M_base_size; while (l < r) { if (l & 1) M_c[l] = M_op2(std::move(M_c[l]), x), ++l; if (r & 1) --r, M_c[r] = M_op2(std::move(M_c[r]), x); l >>= 1; r >>= 1; } } value_type get(size_type i) const { i += M_base_size; value_type res = M_c[i]; while (i > 1) { i >>= 1; res = M_op1(std::move(res), M_c[i]); } return res; } }; template <typename Tp> struct single_get_range_add { using first_type = Tp; using second_type = Tp; struct binary_operation { first_type identity{}; first_type operator ()(first_type const& x, first_type const& y) const { return x + y; } }; struct external_binary_operation { first_type operator ()(first_type const& x, second_type const& y) const { return x + y; } }; }; #include <cstdio> #include <cstdint> #include <algorithm> #include <utility> #include <vector> int main() { size_t n, q; scanf("%zu %zu", &n, &q); std::vector<intmax_t> a(n); for (auto& ai: a) scanf("%jd", &ai); dual_segment_tree<single_get_range_add<intmax_t>> sg(n); std::vector<intmax_t> b(n); for (size_t i = 0; i < q; ++i) { char c; scanf(" %c", &c); switch (c) { case 'A': { size_t x; intmax_t y; scanf("%zu %jd", &x, &y); --x; b[x] += sg.get(x) * a[x]; sg.modify(x, x+1, -sg.get(x)); a[x] += y; break; } case 'B': { size_t x, y; scanf("%zu %zu", &x, &y); --x, --y; sg.modify(x, y+1, 1); break; } } } for (size_t i = 0; i < n; ++i) { b[i] += sg.get(i) * a[i]; } for (size_t i = 0; i < n; ++i) printf("%jd%c", b[i], i+1<n? ' ': '\n'); }