結果

問題 No.877 Range ReLU Query
ユーザー 37zigen37zigen
提出日時 2019-09-07 12:31:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 375 ms / 2,000 ms
コード長 1,862 bytes
コンパイル時間 1,290 ms
コンパイル使用メモリ 93,696 KB
実行使用メモリ 15,892 KB
最終ジャッジ日時 2024-04-25 22:10:03
合計ジャッジ時間 6,296 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 4 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 364 ms
14,652 KB
testcase_12 AC 314 ms
15,448 KB
testcase_13 AC 255 ms
11,184 KB
testcase_14 AC 268 ms
11,208 KB
testcase_15 AC 375 ms
15,176 KB
testcase_16 AC 369 ms
14,852 KB
testcase_17 AC 368 ms
14,884 KB
testcase_18 AC 366 ms
15,008 KB
testcase_19 AC 315 ms
15,216 KB
testcase_20 AC 345 ms
15,892 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <queue>

struct Seg {
  int n;
  std::vector<long long> v;
  
  Seg(int n_) {
    n = 1;
    while (n < n_) {
      n *= 2;
    }
    v.assign(2*n-1, 0);
  }

  void setVal(int k, long long val) {
    k += n-1;
    v[k] = val;
    while(k > 0) {
      k = (k - 1)/2;
      v[k] = v[2*k+1] + v[2*k+2];
    }
  }

  long long query(int a, int b) {
    return query(0, n, a, b, 0);
  }

  long long query(int l, int r, int a, int b, int k) {
    if (r <= a || b <= l) return 0;
    else if (a <= l && r <= b) return v[k];
    else {
      long long vl = query(l, (l + r)/2, a, b, 2*k+1);
      long long vr = query((l+r)/2, r, a, b, 2*k+2);
      return vl+vr;
    }
  }
  
};

int main() {
  int N, Q;
  std::cin >> N >> Q;
  std::vector<long long> a(N);
  std::vector<long long> ans(Q);
  std::priority_queue<std::pair<long long, int>> pq;
  Seg seg(N);
  Seg seg2(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> a[i];
    pq.push(std::make_pair(-a[i], i));
    seg.setVal(i, a[i]);
    seg2.setVal(i, 1);
  }
  std::vector<std::tuple<long long, int, int, int>> q;
  for (int i = 0; i < Q; ++i) {
    int t, l, r;
    long long x;
    std::cin >> t >> l >> r >> x;
    --l;--r;
    q.push_back(std::make_tuple(x, l, r, i));
  }
  std::sort(q.begin(), q.end());
  for (int i = 0; i < Q; ++i) {
    long long x = std::get<0>(q[i]);
    int l       = std::get<1>(q[i]);
    int r       = std::get<2>(q[i]);
    int idx     = std::get<3>(q[i]);
    while (!pq.empty()) {
      if (-pq.top().first > x) break;
      else {
	std::pair<long long, int> p = pq.top();
	pq.pop();
	seg.setVal(p.second, 0);
	seg2.setVal(p.second, 0);
      }
    }
    ans[idx] = seg.query(l, r+1) - x*seg2.query(l, r+1);
  }
  for (int i = 0; i < Q; ++i) {
    std::cout << ans[i] << std::endl;
  }
}
0