結果
問題 | No.877 Range ReLU Query |
ユーザー |
|
提出日時 | 2019-12-07 06:53:23 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,577 bytes |
コンパイル時間 | 497 ms |
コンパイル使用メモリ | 43,208 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-11-08 10:24:11 |
合計ジャッジ時間 | 2,749 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 20 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:45:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 45 | scanf("%d%d", &n, &q); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:46:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 46 | for (int i = 1; i <= n; i++) scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:47:43: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 47 | for (int i = 1; i <= q; i++) scanf("%d%d%d%d", &k, &query[i].l, &query[i].r, &query[i].x); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <algorithm> #include <string.h> #include <utility> using namespace std; #define F first #define S second constexpr int kN = int(1E5 + 10); typedef long long int ll; struct Query { int l, r, x, id; }; struct BIT { ll val[kN]; void init() {memset(val, 0, sizeof(val));} void add(int pos, int x) { while (pos < kN) { val[pos] += x; pos += pos & -pos; } return ; } ll ask(int pos) { ll ans = 0; while (pos) { ans += val[pos]; pos ^= pos & -pos; } return ans; } }; bool cmp(Query a, Query b) {return a.x < b.x;} BIT cnt, tot; int a[kN]; ll ans[kN]; pair<int, int> na[kN]; Query query[kN]; int main() { int n, q, k, now = 1; scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= q; i++) scanf("%d%d%d%d", &k, &query[i].l, &query[i].r, &query[i].x); for (int i = 1; i <= q; i++) query[i].id = i; cnt.init(); tot.init(); for (int i = 1; i <= n; i++) tot.add(i, a[i]); for (int i = 1; i <= n; i++) cnt.add(i, 1); for (int i = 1; i <= n; i++) na[i] = {a[i], i}; sort(na + 1, na + n + 1); sort(query + 1, query + q + 1, cmp); for (int i = 1; i <= q; i++) { while (now <= n) { if (na[now].F < query[i].x) { cnt.add(na[now].S, -1); tot.add(na[now].S, -na[now].F); now++; } else break; } ans[query[i].id] = tot.ask(query[i].r) - tot.ask(query[i].l - 1) - (cnt.ask(query[i].r) - cnt.ask(query[i].l - 1)) * query[i].x; } for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]); }