結果
問題 | No.877 Range ReLU Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 23:53:19 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 704 ms / 2,000 ms |
コード長 | 3,037 bytes |
コンパイル時間 | 1,447 ms |
コンパイル使用メモリ | 99,072 KB |
実行使用メモリ | 62,848 KB |
最終ジャッジ日時 | 2024-11-08 10:11:52 |
合計ジャッジ時間 | 8,779 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 5 ms
5,248 KB |
testcase_02 | AC | 4 ms
5,248 KB |
testcase_03 | AC | 4 ms
5,248 KB |
testcase_04 | AC | 3 ms
5,248 KB |
testcase_05 | AC | 3 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 3 ms
5,248 KB |
testcase_08 | AC | 5 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 4 ms
5,248 KB |
testcase_11 | AC | 657 ms
62,720 KB |
testcase_12 | AC | 583 ms
62,720 KB |
testcase_13 | AC | 421 ms
32,000 KB |
testcase_14 | AC | 450 ms
32,000 KB |
testcase_15 | AC | 704 ms
62,848 KB |
testcase_16 | AC | 691 ms
62,720 KB |
testcase_17 | AC | 687 ms
62,720 KB |
testcase_18 | AC | 688 ms
62,720 KB |
testcase_19 | AC | 453 ms
62,720 KB |
testcase_20 | AC | 599 ms
62,720 KB |
ソースコード
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <functional> #include <algorithm> #include <string> #include <vector> #include <set> #include <map> #include <queue> #include <stack> using namespace std; template<class T, class Compare = less<T> > using MaxHeap = priority_queue<T, vector<T>, Compare>; template<class T, class Compare = greater<T> > using MinHeap = priority_queue<T, vector<T>, Compare>; using llong = long long; llong n, q; llong key; vector<vector<llong> >seg; vector<vector<llong> >sum; void init(llong &n) { llong _n = 1; while (_n < n) { _n *= 2; } n = _n; seg.assign(2 * n, vector<llong>(1, 0)); sum.assign(2 * n, vector<llong>(1, 0)); for (int i = n - 2; i >= 0; i--) { seg[i].resize(seg[2 * i + 1].size() + seg[2 * i + 2].size(), 0); sum[i].assign(sum[2 * i + 1].size() + sum[2 * i + 2].size(), 0); } return; }; void setv(llong k, llong v) { k += n - 1; seg[k][0] = v; sum[k][0] = v; }; void build() { for (int i = n - 2; i >= 0; i--) { auto &l = seg[i * 2 + 1]; auto &r = seg[i * 2 + 2]; int l_i = 0; int r_i = 0; for (int j = 0; j < seg[i].size(); j++) { if (l_i >= l.size()) seg[i][j] = r[r_i++]; else if (r_i >= r.size()) seg[i][j] = l[l_i++]; else if (l[l_i] < r[r_i]) seg[i][j] = l[l_i++]; else seg[i][j] = r[r_i++]; } sort(seg[i].begin(), seg[i].end()); sum[i][0] = seg[i][0]; for (int j = 1; j < sum[i].size(); j++) { sum[i][j] = sum[i][j - 1] + seg[i][j]; } } } pair<llong, llong> acc(llong k, llong l, llong r) { llong idx = upper_bound(seg[k].begin(), seg[k].end(), key) - seg[k].begin(); if (idx >= 1) { return make_pair(sum[k].back() - sum[k][idx - 1], sum[k].size() - idx); } else { return make_pair(sum[k].back(), sum[k].size()); } }; pair<llong, llong> query(llong l, llong r, llong k, llong a, llong b) { if (b <= l || r <= a) return make_pair(0, 0); if (l <= a && b <= r) { return acc(k, a, b); } else { pair<llong, llong> v1 = query(l, r, 2 * k + 1, a, (a + b) / 2); pair<llong, llong> v2 = query(l, r, 2 * k + 2, (a + b) / 2, b); return make_pair(v1.first + v2.first, v1.second + v2.second); } }; int main() { cin >> n >> q; llong nn = n; init(n); for (int i = 0; i < nn; i++) { llong v; cin >> v; setv(i, v); } build(); /* for (int k = 0; k < 2 * n; k++) { cout << k << ':'; for (int i = 0; i < seg[k].size(); i++) { cout << seg[k][i] << ' '; } cout << endl; } */ for (int i = 0; i < q; i++) { llong com, l, r, a; cin >> com >> l >> r >> a; key = a; l--; r--; pair<llong, llong> b = query(l, r + 1, 0, 0, n); cout << b.first - (key * b.second) << endl; } return 0; }