結果
問題 |
No.2758 RDQ
|
ユーザー |
![]() |
提出日時 | 2024-05-17 22:16:18 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 1,365 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 31,104 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 15:45:56 |
合計ジャッジ時間 | 3,130 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <stdio.h> #include <stdlib.h> int cmp_int (const void *ap, const void *bp) { int a = *(int *)ap; int b = *(int *)bp; if (a < b) { return -1; } if (a > b) { return 1; } return 0; } int main () { int n = 0; int q = 0; int a[50000] = {}; int l[50000][2] = {}; int r[50000][2] = {}; int k[50000] = {}; int res = 0; int ans[50000][2] = {}; int idx1 = 0; int idx2 = 0; int cnt[100000] = {}; res = scanf("%d", &n); res = scanf("%d", &q); for (int i = 0; i < n; i++) { res = scanf("%d", a+i); } for (int i = 0; i < q; i++) { res = scanf("%d", l[i]); res = scanf("%d", r[i]); res = scanf("%d", k+i); l[i][0]--; l[i][1] = i; r[i][0]--; r[i][1] = i; } qsort(l, q, sizeof(int)*2, cmp_int); qsort(r, q, sizeof(int)*2, cmp_int); for (int i = 0; i < n; i++) { while (idx1 < q && l[idx1][0] <= i) { ans[l[idx1][1]][0] = cnt[k[l[idx1][1]]-1]; idx1++; } for (int p = 1; p*p <= a[i]; p++) { if (a[i]%p == 0) { cnt[p-1]++; if (p*p != a[i]) { cnt[a[i]/p-1]++; } } } while (idx2 < q && r[idx2][0] <= i) { ans[r[idx2][1]][1] = cnt[k[r[idx2][1]]-1]; idx2++; } } for (int i = 0; i < q; i++) { printf("%d\n", ans[i][1]-ans[i][0]); } return 0; }