結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 22:25:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 386 ms / 2,000 ms |
コード長 | 2,269 bytes |
コンパイル時間 | 1,426 ms |
コンパイル使用メモリ | 114,572 KB |
実行使用メモリ | 15,144 KB |
最終ジャッジ日時 | 2024-11-16 04:20:50 |
合計ジャッジ時間 | 10,261 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <map>#include <queue>#include <set>#include <random>using namespace std;typedef long long ll;#define rep(i, n) for(int i = 0; i < (n); i++)template<class T>using vi = vector<T>;template<class T>using vii = vector<vi<T>>;template<class T>using viii = vector<vii<T>>;using pii = pair<int, int>;template<class T>struct segtree {int n;vector<T> d;const T e = 0;segtree(int n_ = 0) {n = 1;while (n < n_) n <<= 1;d.resize(2 * n - 1, e);}T op(T a, T b) { return a + b; }void update(int i, T x) {int idx = i + n - 1;d[idx] = x;while (idx) {idx = (idx - 1) / 2;d[idx] = op(d[2 * idx + 1], d[2 * idx + 2]);}return;}void add(int i, T x) {int idx = i + n - 1;d[idx] += x;while (idx) {idx = (idx - 1) / 2;d[idx] = op(d[2 * idx + 1], d[2 * idx + 2]);}return;}T get(int l, int r) { return get_sub(l, r, 0, 0, n); }T get_sub(int l, int r, int i, int ok, int ng) {if (l <= ok && ng <= r) return d[i];if (r <= ok || ng <= l) return e;int mid = (ok + ng) / 2;T vl = get_sub(l, r, 2 * i + 1, ok, mid);T vr = get_sub(l, r, 2 * i + 2, mid, ng);return op(vl, vr);}};using tii = tuple<ll, int, int>;int main(){int n, q;cin >> n >> q;vi<ll> a(n), l(q), r(q), x(q);rep(i, n) cin >> a[i];rep(i, q) cin >> l[i] >> r[i] >> x[i];rep(i, q) l[i]--;vi<tii> d;rep(i, n) d.push_back({ a[i], 0, i });rep(i, q) d.push_back({ x[i], 1, i });sort(d.begin(), d.end());segtree<ll> seg(n + 10), segn(n + 10);vi<ll> ans(q);rep(i, n + q) {ll num, ax, pos;tie(num, ax, pos) = d[i];if (ax == 0) {seg.add(pos, num);segn.add(pos, 1);}else if (ax == 1) {ll acum = seg.get(l[pos], r[pos]);ll cnt = segn.get(l[pos], r[pos]);ans[pos] = acum + x[pos] * (r[pos] - l[pos] - cnt);}}for (ll res : ans) cout << res << endl;return 0;}