結果

問題 No.877 Range ReLU Query
ユーザー 37zigen
提出日時 2019-09-07 12:31:48
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 405 ms / 2,000 ms
コード長 1,862 bytes
コンパイル時間 1,367 ms
コンパイル使用メモリ 94,136 KB
実行使用メモリ 15,136 KB
最終ジャッジ日時 2024-11-08 10:15:00
合計ジャッジ時間 6,663 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

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