結果
問題 | No.2500 Products in a Range |
ユーザー |
👑 ![]() |
提出日時 | 2023-09-02 20:05:31 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,969 bytes |
コンパイル時間 | 2,172 ms |
コンパイル使用メモリ | 136,664 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-12 06:12:27 |
合計ジャッジ時間 | 2,836 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 41 WA * 20 |
ソースコード
#include <algorithm>#include <bit>#include <cassert>#include <cstdint>#include <functional>#include <iostream>#include <numeric>#include <vector>namespace emthrm {template <typename Band>struct SparseTable {using BinOp = std::function<Band(Band, Band)>;SparseTable() = default;explicit SparseTable(const std::vector<Band>& a, const BinOp bin_op) {init(a, bin_op);}void init(const std::vector<Band>& a, const BinOp bin_op_) {bin_op = bin_op_;const int n = a.size();assert(n > 0);lg.assign(n + 1, 0);for (int i = 2; i <= n; ++i) {lg[i] = lg[i >> 1] + 1;}const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1;data.assign(table_h, std::vector<Band>(n));std::copy(a.begin(), a.end(), data.front().begin());for (int i = 1; i < table_h; ++i) {for (int j = 0; j + (1 << i) <= n; ++j) {data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);}}}Band query(const int left, const int right) const {assert(left < right);const int h = lg[right - left];return bin_op(data[h][left], data[h][right - (1 << h)]);}private:BinOp bin_op;std::vector<int> lg;std::vector<std::vector<Band>> data;};} // namespace emthrm// <WA> #910622 ベースint main() {constexpr int kMaxN = 5000, kMinA = -1000000000, kMaxA = 1000000000;int n, l, r;std::cin >> n >> l >> r;assert(1 <= n && n <= kMaxN && kMinA <= l && l <= r && r <= kMaxA);std::vector<std::int64_t> a(n);for (int i = 0; i < n; ++i) {std::cin >> a[i];assert(kMinA <= a[i] && a[i] <= kMaxA);}std::ranges::sort(a);std::vector<int> p_prime(n, n), q(n, -1), q_prime(n);for (int i = 0; i < n; ++i) {if (a[i] < 0) {for (int lb = -1; lb + 1 < p_prime[i];) {const int p = std::midpoint(lb, p_prime[i]);(a[i] * a[p] <= r ? p_prime[i] : lb) = p;}for (int ub = n; q[i] + 1 < ub;) {const int cand_q = std::midpoint(q[i], ub);(a[i] * a[cand_q] >= l ? q[i] : ub) = cand_q;}} else {for (int lb = -1; lb + 1 < p_prime[i];) {const int p = std::midpoint(lb, p_prime[i]);(a[i] * a[p] >= l ? p_prime[i] : lb) = p;}for (int ub = n; q[i] + 1 < ub;) {const int cand_q = std::midpoint(q[i], ub);(a[i] * a[cand_q] <= r ? q[i] : ub) = cand_q;}}if (q[i] < p_prime[i]) {p_prime[i] = n;q[i] = -1;} else {p_prime[i] = std::max(p_prime[i], i + 1);}q_prime[i] = std::min(q[i], i - 1);}int ans = 1;const emthrm::SparseTable<int> sparse_table(q_prime, [](const int x, const int y) -> int { return std::max(x, y); });for (int i = 0; i < n; ++i) {if (p_prime[i] < q[i]) {const int f = 3 - p_prime[i] + sparse_table.query(p_prime[i], q[i]);ans = std::max({ans, f, 2});}}std::cout << ans << '\n';return 0;}