#795077 (C++14) No.2065 Sum of Min

• 問題: No.2065 Sum of Min
• ユーザー: QCFium
• 提出日時: 2022-09-02 23:35:12
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 42 ms / 2,000 ms
• コード長: 3,336 bytes
• コンパイル時間: 1,955 ms
• コンパイル使用メモリ: 184,364 KB
• 実行使用メモリ: 9,600 KB
• 最終ジャッジ日時: 2024-11-16 06:34:29
• 合計ジャッジ時間: 4,968 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,820 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	2 ms; 6,816 KB
testcase_04	AC	27 ms; 9,472 KB
testcase_05	AC	27 ms; 9,344 KB
testcase_06	AC	30 ms; 9,216 KB
testcase_07	AC	22 ms; 9,472 KB
testcase_08	AC	33 ms; 9,472 KB
testcase_09	AC	39 ms; 9,472 KB
testcase_10	AC	37 ms; 9,472 KB
testcase_11	AC	38 ms; 9,472 KB
testcase_12	AC	41 ms; 9,472 KB
testcase_13	AC	42 ms; 9,600 KB
testcase_14	AC	40 ms; 9,472 KB
testcase_15	AC	41 ms; 9,472 KB
testcase_16	AC	42 ms; 9,472 KB
testcase_17	AC	42 ms; 9,344 KB
testcase_18	AC	41 ms; 9,600 KB
testcase_19	AC	42 ms; 9,472 KB
testcase_20	AC	42 ms; 9,472 KB
testcase_21	AC	41 ms; 9,344 KB

ソースコード

#include <bits/stdc++.h>

struct FastI {
	char buf[1000000];
	char *ptr = buf, *end;
	void read_() { end = (ptr = buf) + fread(buf, 1, sizeof(buf) - 1, stdin); }
	FastI () { read_(); }
	void inc() { if (++ptr == end) read_(); }
	template<typename value_t> value_t read() {
		bool neg = false;
		value_t res = 0;
		while ((*ptr < '0' || *ptr > '9') && *ptr != '-') inc();
		if (*ptr == '-') neg = true, inc();
		while (*ptr >= '0' && *ptr <= '9') res = res * 10 + *ptr - '0', inc();
		return neg ? -res : res;
	}
} fasti;
#define ri fasti.read<int>
#define rs64 fasti.read<int64_t>

struct FastO {
	char buf[1000000];
	char *ptr = buf;
	void write_() { fwrite(buf, 1, ptr - buf, stdout); ptr = buf; }
	~FastO () { write_(); }
	void print(char c) { *ptr = c; if (++ptr == std::end(buf)) write_(); }
	void print(const std::string &s) { for (auto c : s) print(c); }
	template<typename str_t> auto print(str_t s) -> decltype(std::string(s), void()) { print(std::string(s)); }
	template<typename value_t> typename std::enable_if_t<std::is_integral<value_t>::value> print(value_t val) {
		static char tmp_buf[32];
		if (val < 0) print('-'), val = -val;
		char *head = std::end(tmp_buf);
		if (val == 0) *--head = '0';
		else while (val) *--head = '0' + val % 10, val /= 10;
		int size = std::end(tmp_buf) - head;
		if (std::end(buf) - ptr <= size) write_();
		memcpy(ptr, head, size);
		ptr += size;
	}
	template<typename A, typename... B> void print(A a, B... b) { print(a); print(b...); }
	template<typename... A> void println(A... a) { print(a..., '\n'); }
} fasto;
#define print fasto.print
#define println fasto.println



template<typename value_t> struct BIT {
	int n;
	value_t all_sum = 0;
	std::vector<value_t> data;
	BIT (int n) : n(n), data(n + 1) {}
	template<class S = value_t> BIT (const std::vector<S> &a) : n(a.size()), data(n + 1) {
		std::copy(a.begin(), a.end(), data.begin() + 1);
		all_sum = std::accumulate(a.begin(), a.end(), (value_t) 0);
		for (int i = 1; i < n; i++) if (i + (i & -i) <= n) data[i + (i & -i)] += data[i];
	}
	void add(int i, value_t val) {
		for (i++; i <= n; i += i & -i) data[i] += val;
		all_sum += val;
	}
	value_t sum(int r) {
		value_t res = 0;
		for (; r; r -= r & -r) res += data[r];
		return res;
	}
	value_t sum(int l, int r) { return sum(r) - sum(l); }
	value_t sum_right(int l) { return all_sum - sum(l); }
};

int main() {
	int n = ri();
	int q = ri();
	std::vector<int> a(n);
	std::vector<std::pair<int, int> > p(n);
	for (int i = 0; i < n; i++) {
		a[i] = ri();
		p[i] = {a[i], i};
	}
	std::sort(p.begin(), p.end());
	int head = n - 1;
	
	struct Query {
		int l;
		int r;
		int x;
		int id;
	};
	std::pair<int, int> qinfo[q];
	std::pair<int, int> qs[q];
	for (int i = 0; i < q; i++) {
		qinfo[i].first = ri() - 1;
		qinfo[i].second = ri();
		qs[i].first = ri();
		qs[i].second = i;
	}
	std::sort(qs, qs + q, [] (auto &i, auto &j) { return i.first > j.first; });
	
	BIT<uint64_t> tree(a);
	
	std::vector<int64_t> res(q);
	for (auto &i : qs) {
		while (head >= 0 && p[head].first >= i.first) {
			tree.add(p[head].second, 100000000000001 - a[p[head].second]);
			head--;
		}
		auto tmp = tree.sum(qinfo[i.second].first, qinfo[i.second].second);
		res[i.second] = (int64_t) i.first * (tmp / 100000000000001ULL) + tmp % 100000000000001ULL;
	}
	for (auto i : res) println(i);
	
	return 0;
}