結果
問題 | No.2500 Products in a Range |
ユーザー |
![]() |
提出日時 | 2023-10-13 22:07:24 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 3,009 bytes |
コンパイル時間 | 1,293 ms |
コンパイル使用メモリ | 31,832 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 17:48:38 |
合計ジャッジ時間 | 3,080 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 61 |
ソースコード
#include <stdio.h>#include <stdlib.h>int cmp_ll (const void *ap, const void *bp) {long long a = *(long long *)ap;long long b = *(long long *)bp;if (a < b) {return -1;}if (a > b) {return 1;}return 0;}int main () {int n = 0;long long l = 0LL;long long r = 0LL;long long a[5000] = {};int res = 0;int ans = 1;long long tl[5000] = {};long long tr[5000] = {};res = scanf("%d", &n);res = scanf("%lld", &l);res = scanf("%lld", &r);for (int i = 0; i < n; i++) {res = scanf("%lld", a+i);}qsort(a, n, sizeof(long long), cmp_ll);for (int i = 0; i < n; i++) {if (a[i] < 0LL) {long long tmp[2] = { -1000000001LL, 1000000001LL };while (tmp[1]-tmp[0] > 1LL) {long long nxt = (tmp[0]+tmp[1])/2LL;if (nxt*a[i] >= l) {tmp[0] = nxt;} else {tmp[1] = nxt;}}tl[i] = tmp[0];tmp[0] = -1000000001LL;tmp[1] = 1000000001LL;while (tmp[1]-tmp[0] > 1LL) {long long nxt = (tmp[0]+tmp[1])/2LL;if (nxt*a[i] <= r) {tmp[1] = nxt;} else {tmp[0] = nxt;}}tr[i] = tmp[1];} else {long long tmp[2] = { -1000000001LL, 1000000001LL };while (tmp[1]-tmp[0] > 1LL) {long long nxt = (tmp[0]+tmp[1])/2LL;if (nxt*a[i] >= l) {tmp[1] = nxt;} else {tmp[0] = nxt;}}tl[i] = tmp[1];tmp[0] = -1000000001LL;tmp[1] = 1000000001LL;while (tmp[1]-tmp[0] > 1LL) {long long nxt = (tmp[0]+tmp[1])/2LL;if (nxt*a[i] <= r) {tmp[0] = nxt;} else {tmp[1] = nxt;}}tr[i] = tmp[0];}}for (int i = 0; i < n-1; i++) {for (int j = i+1; j < n; j++) {if (ans < 2 && a[i]*a[j] >= l && a[i]*a[j] <= r) {ans = 2;}if (j-i+1 >= ans && a[i]*a[i+1] >= l && a[i]*a[i+1] <= r && a[i]*a[j] >= l && a[i]*a[j] <= r && a[j]*a[j-1] >= l && a[j]*a[j-1] <= r) {long long cl = tl[i];long long cr = tr[i];int idx[2] = { -1, i };ans = j-i+1;if (cr > tr[j]) {cr = tr[j];}if (cl < tl[j]) {cl = tl[j];}while (idx[1]-idx[0] > 1) {int nxt = (idx[0]+idx[1])/2;if (a[nxt] < cl) {idx[0] = nxt;} else {idx[1] = nxt;}}if (idx[1] < i && a[idx[1]] >= cl && a[idx[1]] <= cr) {ans = j-i+2;}idx[0] = j;idx[1] = n;while (idx[1]-idx[0] > 1) {int nxt = (idx[0]+idx[1])/2;if (a[nxt] < cl) {idx[0] = nxt;} else {idx[1] = nxt;}}if (idx[1] < n && a[idx[1]] >= cl && a[idx[1]] <= cr) {ans = j-i+2;}}}}printf("%d\n", ans);return 0;}