結果
問題 | No.2500 Products in a Range |
ユーザー |
👑 ![]() |
提出日時 | 2023-09-02 17:44:11 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,752 bytes |
コンパイル時間 | 1,198 ms |
コンパイル使用メモリ | 113,376 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 13:55:01 |
合計ジャッジ時間 | 2,793 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
#include <algorithm>#include <cassert>#include <cstdint>#include <iostream>#include <numeric>#include <vector>// <AC>// 連続する部分列のみ考える O(n log n) 時間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);int ans = 1;std::vector<int> p(n, n), q(n, -1);for (int i = 0; i < n; ++i) {if (a[i] < 0) {for (int lb = -1; lb + 1 < p[i];) {const int cand_p = std::midpoint(lb, p[i]);(a[i] * a[cand_p] <= r ? p[i] : lb) = cand_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[i];) {const int cand_p = std::midpoint(lb, p[i]);(a[i] * a[cand_p] >= l ? p[i] : lb) = cand_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[i]) {p[i] = n;q[i] = -1;} else if (p[i] != i || q[i] != i) {ans = 2;}}for (int i = 0; i + 1 < n; ++i) {if (p[i] <= i + 1) {int j = i;for (int ub = q[i] + 1; j + 1 < ub;) {const int cand_j = std::midpoint(j, ub);(p[cand_j] <= i && cand_j - 1 <= q[cand_j] ? j : ub) = cand_j;}ans = std::max(ans, j - i + 1);}}std::cout << ans << '\n';return 0;}