結果
| 問題 | No.878 Range High-Element Query |
| ユーザー |
 rsk0315
|
| 提出日時 | 2019-09-06 21:56:05 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,594 bytes |
| コンパイル時間 | 759 ms |
| コンパイル使用メモリ | 65,492 KB |
| 実行使用メモリ | 10,304 KB |
| 最終ジャッジ日時 | 2023-09-06 23:42:13 |
| 合計ジャッジ時間 | 2,366 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
ソースコード
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <tuple>
constexpr intmax_t operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t operator ""_zu(unsigned long long n) { return n; }
// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }
template <
typename Monoid,
typename Container = std::vector<typename Monoid::first_type>
>
class basic_segment_tree {
public:
using size_type = size_t;
using first_type = typename Monoid::first_type;
using second_type = typename Monoid::second_type;
using value_type = first_type;
using binary_operation = typename Monoid::binary_operation;
using external_binary_operation = typename Monoid::external_binary_operation;
using container = Container;
private:
size_type M_base_size;
binary_operation M_op1;
external_binary_operation M_op2;
container M_c;
template <typename Predicate>
size_type M_search_root(Predicate pred, value_type& x) const {
size_type n = M_base_size;
size_type l = n;
size_type r = n+n;
size_type v = r;
std::vector<size_type> rs;
x = M_op1.identity;
while (l < r) {
if (l & 1) {
if (!pred(M_op1(x, M_c[l]))) return l;
x = M_op1(x, M_c[l++]);
}
if (r & 1) rs.push_back(--r);
l >>= 1;
r >>= 1;
}
while (!rs.empty()) {
size_type r = rs.back();
rs.pop_back();
if (!pred(M_op1(x, M_c[r]))) return r;
x = M_op1(x, M_c[r]);
}
return v;
}
template <typename Predicate>
size_type M_search_leaf(Predicate pred, size_type v, value_type& x) const {
size_type n = M_base_size;
while (v < n) {
size_type c = v << 1;
if (pred(M_op1(x, M_c[c]))) {
x = M_op1(x, M_c[c]);
c |= 1;
}
v = c;
}
return v - n;
}
public:
basic_segment_tree() = default;
basic_segment_tree(basic_segment_tree const&) = default;
basic_segment_tree(basic_segment_tree&&) = default;
basic_segment_tree(size_type n, first_type const& x = binary_operation().identity):
M_base_size(n),
M_op1(binary_operation()),
M_op2(external_binary_operation()),
M_c(n+n, x)
{
for (size_type i = n; i--;)
M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
}
template <typename InputIt>
basic_segment_tree(InputIt first, InputIt last):
M_op1(binary_operation()), M_op2(external_binary_operation())
{ assign(first, last); }
basic_segment_tree& operator =(basic_segment_tree const&) = default;
basic_segment_tree& operator =(basic_segment_tree&&) = default;
void assign(size_type n, value_type const& x) {
M_base_size = n;
M_c.assign(n+n, x);
for (size_type i = n; i--;)
M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
}
template <typename InputIt>
void assign(InputIt first, InputIt last) {
container tmp(first, last);
M_base_size = tmp.size();
M_c.resize(M_base_size);
M_c.insert(M_c.end(), tmp.begin(), tmp.end());
for (size_type i = M_base_size; i--;)
M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
}
void modify(size_type i, second_type const& x) {
i += M_base_size;
M_c[i] = M_op2(M_c[i], x);
while (i > 1) {
i >>= 1;
M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
}
}
void assign_at(size_type i, value_type const& x) {
i += M_base_size;
M_c[i] = x;
while (i > 1) {
i >>= 1;
M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
}
}
value_type const& operator [](size_type i) const { return M_c[i + M_base_size]; }
value_type accumulate(size_type l, size_type r) {
first_type resl = M_op1.identity;
first_type resr = resl;
l += M_base_size;
r += M_base_size;
while (l < r) {
if (l & 1) resl = M_op1(resl, M_c[l++]);
if (r & 1) resr = M_op1(M_c[--r], resr);
l >>= 1;
r >>= 1;
}
return M_op1(resl, resr);
}
template <typename Predicate>
std::pair<size_type, value_type> partition_point(Predicate pred) const {
value_type value;
size_type root = M_search_root(pred, value);
size_type bound = M_search_leaf(pred, root, value);
return {bound, value};
}
};
template <typename Tp>
struct range_high_query {
using first_type = std::tuple<Tp, size_t>; // max (self), count
using second_type = Tp;
struct binary_operation {
first_type identity{};
first_type operator ()(first_type const& x, first_type const& y) const {
int x0, y0;
size_t x1, y1;
std::tie(x0, x1) = x;
std::tie(y0, y1) = y;
if (x0 < y0) {
return {y0, x1+y1};
} else {
return {x0, x1};
}
}
};
struct external_binary_operation {
first_type operator ()(first_type const& x, second_type const&) const {
return x;
}
};
};
int main() {
size_t n, q;
scanf("%zu %zu", &n, &q);
std::vector<std::tuple<int, size_t>> a(n);
for (auto& ai: a) {
int tmp;
scanf("%d", &tmp);
ai = std::make_tuple(tmp, 1);
}
basic_segment_tree<range_high_query<int>> st(a.begin(), a.end());
for (size_t i = 0; i < q; ++i) {
size_t l, r;
scanf(" 1 %zu %zu", &l, &r);
--l, --r;
// fprintf(stderr, "[%zu, %zu)\n", l, r+1);
printf("%zu\n", std::get<size_t>(st.accumulate(l, r+1)));
}
// for (size_t i = 0; i < n; ++i)
// for (size_t j = 0; j <= i; ++j) {
// int x0;
// size_t x1;
// std::tie(x0, x1) = st.accumulate(j, i+1);
// fprintf(stderr, "[%zu, %zu): %d, %zu\n",
// j, i+1, x0, x1);
// }
}