結果

問題 No.2065 Sum of Min
ユーザー QCFiumQCFium
提出日時 2022-09-02 23:10:45
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 66 ms / 2,000 ms
コード長 4,466 bytes
コンパイル時間 2,179 ms
コンパイル使用メモリ 183,496 KB
実行使用メモリ 11,904 KB
最終ジャッジ日時 2024-11-16 06:02:20
合計ジャッジ時間 5,568 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 42 ms
11,776 KB
testcase_05 AC 33 ms
11,776 KB
testcase_06 AC 54 ms
11,520 KB
testcase_07 AC 29 ms
11,776 KB
testcase_08 AC 58 ms
11,648 KB
testcase_09 AC 39 ms
11,776 KB
testcase_10 AC 44 ms
11,776 KB
testcase_11 AC 45 ms
11,776 KB
testcase_12 AC 64 ms
11,776 KB
testcase_13 AC 65 ms
11,776 KB
testcase_14 AC 66 ms
11,776 KB
testcase_15 AC 65 ms
11,904 KB
testcase_16 AC 64 ms
11,776 KB
testcase_17 AC 65 ms
11,776 KB
testcase_18 AC 65 ms
11,776 KB
testcase_19 AC 65 ms
11,776 KB
testcase_20 AC 66 ms
11,776 KB
testcase_21 AC 66 ms
11,776 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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<class monoid_t> struct segtree {
	using value_t = decltype(monoid_t::unit());
	static_assert(std::is_same<decltype(monoid_t::op), value_t(value_t, value_t)>::value ||
				  std::is_same<decltype(monoid_t::op), value_t(const value_t &, const value_t &)>::value);
	value_t unit() { return monoid_t::unit(); }
	int n_, n;
	std::vector<value_t> data;
	
	int ceil_power2(int x) { int i = 1; while (i < x) i <<= 1; return i; }
	segtree (int n_) : n_(n_), n(ceil_power2(n_)), data(n << 1, unit()) {}
	template<typename itr_t> segtree (itr_t begin, itr_t end) : segtree(end - begin) {
		std::copy(begin, end, data.begin() + n);
		for (int i = n; --i; ) fetch(i);
	}
	template<typename T = value_t> segtree (const std::vector<T> &a) : segtree(a.begin(), a.end()) {}
	
	void fetch(int i) { data[i] = monoid_t::op(data[i << 1], data[i << 1 | 1]); }
	void assign(int i, const value_t &val) { for (data[i += n] = val; i >>= 1; ) fetch(i); }
	value_t operator [] (int i) { return data[i + n]; }
	void apply(int i, const value_t &val) { for (i += n; i; i >>= 1) data[i] = monoid_t::op(data[i], val); }
	value_t aggregate(int l, int r) {
		value_t left = unit(), right = unit();
		for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if (r & 1) right = monoid_t::op(data[--r], right);
			if (l & 1) left = monoid_t::op(left, data[l++]);
		}
		return monoid_t::op(left, right);
	}
	template<typename lambda_t> int lower_bound(const lambda_t &is_lower) {
		if (is_lower(data[1])) return n_ + 1;
		if (!is_lower(unit())) return 0;
		value_t cur = unit();
		int res = 0;
		for (int size = n, node = 1; size > 1; size >>= 1) {
			value_t next = monoid_t::op(cur, data[node <<= 1]);
			if (is_lower(next)) cur = next, res += size >> 1, node++;
		}
		return res + 1;
	}
	int lower_bound(const value_t &val) { return lower_bound([val] (value_t x) { return x < val; }); }
};


template<typename T> struct add {
	static T unit() { return 0; }
	static T op(T a, T b) { return a + b; }
};

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;
	};
	Query qs[q];
	for (auto &i : qs) i.l = ri() - 1, i.r = ri(), i.x = ri();
	for (int i = 0; i < q; i++) qs[i].id = i;
	std::sort(qs, qs + q, [] (auto &i, auto &j) { return i.x > j.x; });
	
	segtree<add<int> > tree0(n);
	segtree<add<int64_t> > tree1(a);
	
	std::vector<int64_t> res(q);
	for (auto &i : qs) {
		while (head >= 0 && p[head].first >= i.x) {
			tree0.apply(p[head].second, 1);
			tree1.apply(p[head].second, -a[p[head].second]);
			head--;
		}
		res[i.id] = (int64_t) i.x * tree0.aggregate(i.l, i.r) + tree1.aggregate(i.l, i.r);
	}
	for (auto i : res) println(i);
	
	return 0;
}
0