結果
| 問題 |
No.878 Range High-Element Query
|
| ユーザー |
 rsk0315
|
| 提出日時 | 2019-09-06 21:56:05 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,594 bytes |
| コンパイル時間 | 699 ms |
| コンパイル使用メモリ | 64,408 KB |
| 最終ジャッジ日時 | 2025-01-07 16:46:49 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | WA * 18 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:181:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
181 | scanf("%zu %zu", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:186:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
186 | scanf("%d", &tmp);
| ~~~~~^~~~~~~~~~~~
main.cpp:193:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
193 | scanf(" 1 %zu %zu", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#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);
// }
}