結果
問題 | No.2500 Products in a Range |
ユーザー |
![]() |
提出日時 | 2023-10-15 16:14:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,277 ms / 2,000 ms |
コード長 | 1,969 bytes |
コンパイル時間 | 1,749 ms |
コンパイル使用メモリ | 199,392 KB |
最終ジャッジ日時 | 2025-02-17 07:55:21 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/all>using namespace std;//using namespace atcoder;//using mint = modint998244353;//const int mod = 998244353;//using mint = modint1000000007;//const int mod = 1000000007;//const int INF = 1e9;const long long LINF = ((long long)1e18) * 2;#define rep(i, n) for (int i = 0; i < (n); ++i)#define rep2(i,l,r)for(int i=(l);i<(r);++i)#define rrep(i, n) for (int i = (n-1); i >= 0; --i)#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)#define all(x) (x).begin(),(x).end()#define allR(x) (x).rbegin(),(x).rend()#define P pair<int,int>template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }inline long long ceil_div(long long x, long long y) { return x / y + ((x ^ y) > 0 && x % y != 0); }inline long long floor_div(long long x, long long y) { return x / y - ((x ^ y) < 0 && x % y != 0); }int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, l, r; cin >> n >> l >> r;r++;vector<int>a(n);rep(i, n)cin >> a[i];sort(all(a));int ans = 1;rep(i, n)rep2(j, i + 1, n) {long long x = a[i];long long y = a[j];long long xy = x * y;if ((xy < l) || (r <= xy))continue;chmax(ans, 2);// [l,r)auto f = [&](long long n) {if (n > 0) {return pair(ceil_div(l, n), ceil_div(r, n));}else if (0 == n) {if (l <= 0 && 0 < r)return pair(-LINF, LINF);else return pair(0LL, 0LL);}else {return pair(floor_div(r, n) + 1, floor_div(l, n) + 1);}};auto[m1, M1] = f(x);auto[m2, M2] = f(y);long long m = max({ m1,m2,x });long long M = min({ M1,M2,y + 1 });if (m >= M)continue;int cnt = lower_bound(all(a), M) - lower_bound(all(a), m);for (auto z : { x,y }) cnt -= (m <= z && z < M);chmax(ans, cnt + 2);}cout << ans << endl;return 0;}