Submission #224059

#	Time	Username	Problem	Language	Result	Execution time	Memory
224059		cheeheng	Fire (JOI20_ho_t5)	C++14	14 / 100	1091 ms	22776 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;

long long S[200005];
int T[200005];
int L[200005];
int R[200005];
long long ans[200005];

long long val[(1<<20)+5];
long long lazyadd[(1<<20)+5];

int N;

long long prefixSum[1000005];

inline int left1(int x){
    return (x<<1)+1;
}

inline int right1(int x){
    return (x<<1)+2;
}

void init(int i = 0, int s = 1, int e = N){
    int m = (s+e)>>1;
    lazyadd[i] = 0;
    if(s == e){
        val[i] = S[s];
    }else{
        int l = left1(i);
        int r = right1(i);
        init(l, s, m);
        init(r, m+1, e);
        val[i] = max(val[l], val[r]);
    }
}

long long rmq(int x, int y, int i = 0, int s = 1, int e = N){
    int m = (s+e)>>1;
    if(x <= s && e <= y){
        return val[i];
    }

    int l = left1(i);
    int r = right1(i);
    if(x > m){
        return rmq(x, y, r, m+1, e);
    }else if(y <= m){
        return rmq(x, y, l, s, m);
    }else{
        return max(rmq(x, y, r, m+1, e), rmq(x, y, l, s, m));
    }
}

int main(){
    int Q;
    scanf("%d%d", &N, &Q);

    for(int i = 1; i <= N; i ++){
        scanf("%d", &S[i]);
    }

    for(int i = 0; i < Q; i ++){
        scanf("%d%d%d", &T[i], &L[i], &R[i]);
    }

    init();

    prefixSum[0] = 0;
    for(int i = 1; i <= N; i ++){
        prefixSum[i] = prefixSum[i-1] + rmq(max(i-T[0],1), i);
    }

    for(int i = 0; i < Q; i ++){
        int t = T[i];
        int l = L[i];
        int r = R[i];

        if(t == T[0]){
            printf("%lld\n", prefixSum[r]-prefixSum[l-1]);
            continue;
        }

        long long ans = 0;
        for(int j = l; j <= r; j ++){
            //printf("%d ", rmq(max(j-t, 1), j));
            ans += rmq(max(j-t, 1), j);
        }
        //printf("\n");
        printf("%lld\n", ans);
    }
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:61:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d", &S[i]);
                     ~~~~~^
ho_t5.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t5.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &S[i]);
         ~~~~~^~~~~~~~~~~~~
ho_t5.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &T[i], &L[i], &R[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80