結果
問題 |
No.2065 Sum of Min
|
ユーザー |
|
提出日時 | 2022-12-13 20:22:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 306 ms / 2,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 1,005 ms |
コンパイル使用メモリ | 96,460 KB |
最終ジャッジ日時 | 2025-02-09 11:04:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <atcoder/segtree> #include <iostream> using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; ll op(ll a, ll b) { return a + b; } ll e() { return 0; } int main() { int n, q; cin >> n >> q; int a[100005]; P z[100005]; for(int i = 0; i < n; i++) { cin >> a[i]; z[i] = P(a[i], i); } sort(z, z + n); int l[100005], r[100005], x[100005]; P p[100005]; for(int i = 0; i < q; i++) { cin >> l[i] >> r[i] >> x[i]; l[i]--; p[i] = P(x[i], i); } sort(p, p + q); segtree<ll, op, e> sum(n), cnt(n); for(int i = 0; i < n; i++) { cnt.set(i, 1); } ll ans[100005]; int u = 0; for(int t = 0; t < q; t++) { int i = p[t].second; while(u < n && z[u].first <= x[i]) { int j = z[u++].second; sum.set(j, a[j]); cnt.set(j, 0); } ans[i] = sum.prod(l[i], r[i]) + x[i] * cnt.prod(l[i], r[i]); } for(int i = 0; i < q; i++) { cout << ans[i] << endl; } }