結果

問題 No.2758 RDQ
コンテスト
ユーザー 2475057t
提出日時 2024-07-07 22:18:46
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

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