結果
問題 | No.877 Range ReLU Query |
ユーザー |
![]() |
提出日時 | 2019-09-06 23:53:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
ソースコード
#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; }