結果
問題 | No.2065 Sum of Min |
ユーザー |
![]() |
提出日時 | 2022-09-02 23:18:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 3,206 bytes |
コンパイル時間 | 2,128 ms |
コンパイル使用メモリ | 182,752 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-11-16 06:15:35 |
合計ジャッジ時間 | 5,123 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#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.printlntemplate<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;};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; });BIT<uint64_t> tree(a);std::vector<int64_t> res(q);for (auto &i : qs) {while (head >= 0 && p[head].first >= i.x) {tree.add(p[head].second, 100000000000001 - a[p[head].second]);head--;}auto tmp = tree.sum(i.l, i.r);res[i.id] = (int64_t) i.x * (tmp / 100000000000001ULL) + tmp % 100000000000001ULL;}for (auto i : res) println(i);return 0;}