結果
問題 | No.877 Range ReLU Query |
ユーザー | SSRS |
提出日時 | 2021-12-18 18:46:27 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 318 ms / 2,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 2,357 ms |
コンパイル使用メモリ | 178,052 KB |
実行使用メモリ | 11,072 KB |
最終ジャッジ日時 | 2024-04-25 22:33:26 |
合計ジャッジ時間 | 6,789 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 4 ms
6,940 KB |
testcase_02 | AC | 3 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,944 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 4 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 3 ms
6,944 KB |
testcase_11 | AC | 312 ms
9,412 KB |
testcase_12 | AC | 279 ms
9,456 KB |
testcase_13 | AC | 222 ms
7,356 KB |
testcase_14 | AC | 240 ms
9,240 KB |
testcase_15 | AC | 318 ms
11,072 KB |
testcase_16 | AC | 302 ms
9,660 KB |
testcase_17 | AC | 309 ms
10,752 KB |
testcase_18 | AC | 305 ms
10,764 KB |
testcase_19 | AC | 316 ms
9,872 KB |
testcase_20 | AC | 318 ms
9,612 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; struct binary_indexed_tree{ int N; vector<long long> BIT; binary_indexed_tree(vector<int> A){ N = A.size(); BIT = vector<long long>(N + 1, 0); for (int i = 0; i < N; i++){ BIT[i + 1] = A[i]; } for (int i = 1; i < N; i++){ if (i + (i & -i) <= N){ BIT[i + (i & -i)] += BIT[i]; } } } void add(int i, int x){ i++; while (i <= N){ BIT[i] += x; i += i & -i; } } long long sum(int i){ long long ans = 0; while (i > 0){ ans += BIT[i]; i -= i & -i; } return ans; } long long sum(int L, int R){ return sum(R) - sum(L); } }; int main(){ int N, Q; cin >> N >> Q; vector<int> a(N); for (int i = 0; i < N; i++){ cin >> a[i]; } vector<int> l(Q), r(Q), x(Q); for (int i = 0; i < Q; i++){ int t; cin >> t >> l[i] >> r[i] >> x[i]; l[i]--; } binary_indexed_tree BIT1(a), BIT2(vector<int>(N, 1)); vector<tuple<int, int, int>> T; for (int i = 0; i < N; i++){ T.push_back(make_tuple(a[i], 0, i)); } for (int i = 0; i < Q; i++){ T.push_back(make_tuple(x[i], 1, i)); } sort(T.begin(), T.end()); vector<long long> ans(Q); for (int i = 0; i < N + Q; i++){ int X = get<0>(T[i]); int t = get<1>(T[i]); int id = get<2>(T[i]); if (t == 0){ BIT1.add(id, -a[id]); BIT2.add(id, -1); } if (t == 1){ ans[id] = BIT1.sum(l[id], r[id]) - BIT2.sum(l[id], r[id]) * X; } } for (int i = 0; i < Q; i++){ cout << ans[i] << endl; } }