結果

問題 No.2758 RDQ
ユーザー 2475057t2475057t
提出日時 2024-07-07 22:18:46
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,389 bytes
コンパイル時間 262 ms
コンパイル使用メモリ 30,848 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-07 22:18:48
合計ジャッジ時間 1,652 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>

typedef struct SegmentTree {
    int size;
    int *tree;
} SegmentTree;

SegmentTree* createSegmentTree(int N) {
    SegmentTree *st = (SegmentTree *)malloc(sizeof(SegmentTree));
    st->size = 2 * N;
    st->tree = (int *)malloc(st->size * sizeof(int));
    for (int i = 0; i < st->size; i++) {
        st->tree[i] = 0;
    }
    return st;
}

void build(SegmentTree *st, int *a, int N) {
    for (int i = 0; i < N; i++) {
        st->tree[N + i] = a[i];
    }
    for (int i = N - 1; i > 0; --i) {
        st->tree[i] = st->tree[i << 1] + st->tree[i << 1 | 1];
    }
}

int query(SegmentTree *st, int l, int r, int k, int N) {
    int res = 0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
        if (l & 1) res += (st->tree[l++] % k == 0);
        if (r & 1) res += (st->tree[--r] % k == 0);
    }
    return res;
}

int main(void) {
    int N, Q;
    scanf("%d %d", &N, &Q);
    int a[N], l[Q], r[Q], k[Q];
    
    for (int p = 0; p < N; p++) {
        scanf("%d", &a[p]);
    }
    
    for (int q = 0; q < Q; q++) {
        scanf("%d %d %d", &l[q], &r[q], &k[q]);
    }
    
    SegmentTree *st = createSegmentTree(N);
    build(st, a, N);
    
    for (int i = 0; i < Q; i++) {
        int result = query(st, l[i] - 1, r[i], k[i], N);
        printf("%d\n", result);
    }
    
    free(st->tree);
    free(st);
    
    return 0;
}
0