結果
問題 | 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;}