#376305 (C++14) No.877 Range ReLU Query

• 問題: No.877 Range ReLU Query
• ユーザー: e869120
• 提出日時: 2019-09-06 21:44:25
• 言語: C++14 (gcc 12.3.0 + boost 1.83.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	3 ms; 5,248 KB
testcase_02	AC	3 ms; 5,248 KB
testcase_03	AC	3 ms; 5,248 KB
testcase_04	AC	3 ms; 5,248 KB
testcase_05	AC	2 ms; 5,248 KB
testcase_06	AC	3 ms; 5,248 KB
testcase_07	AC	2 ms; 5,248 KB
testcase_08	AC	4 ms; 5,248 KB
testcase_09	AC	2 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	475 ms; 47,908 KB
testcase_12	AC	430 ms; 47,356 KB
testcase_13	AC	322 ms; 32,180 KB
testcase_14	AC	323 ms; 30,288 KB
testcase_15	AC	527 ms; 54,364 KB
testcase_16	AC	516 ms; 53,296 KB
testcase_17	AC	534 ms; 54,108 KB
testcase_18	AC	535 ms; 54,380 KB
testcase_19	AC	262 ms; 55,172 KB
testcase_20	AC	419 ms; 55,048 KB

ソースコード

#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;
}