結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー e869120
提出日時 2019-09-06 21:44:25
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 535 ms / 2,000 ms
コード長 1,650 bytes
コンパイル時間 1,201 ms
コンパイル使用メモリ 85,908 KB
実行使用メモリ 55,172 KB
最終ジャッジ日時 2024-11-08 10:01:09
合計ジャッジ時間 6,889 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

class SegmentTree {
public:
	vector<vector<long long>> dat, ruiseki;
	int size_ = 1;

	void init(vector<long long> A) {
		while (size_ <= A.size()) size_ *= 2;
		dat.resize(size_ * 2, vector<long long>(0, 0));
		ruiseki.resize(size_ * 2, vector<long long>(0, 0));

		for (int i = 0; i < A.size(); i++) {
			int cx = i + size_;
			while (cx >= 1) {
				dat[cx].push_back(A[i]);
				cx >>= 1;
			}
		}
		for (int i = 1; i < size_ * 2; i++) {
			sort(dat[i].begin(), dat[i].end());
			ruiseki[i].resize(dat[i].size() + 1, 0);
			for (int j = 0; j < dat[i].size(); j++) ruiseki[i][j + 1] = ruiseki[i][j] + dat[i][j];
		}
	}
	long long query_(int l, int r, int x, int a, int b, int u) {
		if (l <= a && b <= r) {
			int pos1 = lower_bound(dat[u].begin(), dat[u].end(), 1LL * x) - dat[u].begin();
			long long v1 = (dat[u].size() - pos1);
			long long v2 = ruiseki[u][dat[u].size()] - ruiseki[u][pos1];
			return v2 - 1LL * x * v1;
		}
		if (r <= a || b <= l) return 0;

		long long v1 = query_(l, r, x, a, (a + b) >> 1, u * 2);
		long long v2 = query_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
		return v1 + v2;
	}
	long long query(int l, int r, int x) {
		return query_(l, r, x, 0, size_, 1);
	}
};

long long N, Q; vector<long long>A;
SegmentTree Z;

int main() {
	scanf("%lld%lld", &N, &Q); A.resize(N, 0);
	for (int i = 0; i < N; i++) scanf("%lld", &A[i]);
	Z.init(A);

	for (int i = 0; i < Q; i++) {
		int ty, l, r, x; scanf("%d%d%d%d", &ty, &l, &r, &x); l--; r--;
		long long v = Z.query(l, r + 1, x);
		printf("%lld\n", v);
	}
	return 0;
}
0