結果

問題 No.877 Range ReLU Query
ユーザー e869120e869120
提出日時 2019-09-06 21:44:25
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 503 ms / 2,000 ms
コード長 1,650 bytes
コンパイル時間 1,282 ms
コンパイル使用メモリ 86,660 KB
実行使用メモリ 55,048 KB
最終ジャッジ日時 2024-04-25 21:58:03
合計ジャッジ時間 6,636 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 3 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 441 ms
48,024 KB
testcase_12 AC 391 ms
47,276 KB
testcase_13 AC 300 ms
32,180 KB
testcase_14 AC 302 ms
30,280 KB
testcase_15 AC 500 ms
54,368 KB
testcase_16 AC 487 ms
53,420 KB
testcase_17 AC 503 ms
54,224 KB
testcase_18 AC 496 ms
54,504 KB
testcase_19 AC 246 ms
55,048 KB
testcase_20 AC 390 ms
55,044 KB
権限があれば一括ダウンロードができます

ソースコード

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