Submission #224056

#	Time	Username	Problem	Language	Result	Execution time	Memory
224056		cheeheng	Fire (JOI20_ho_t5)	C++14	8 / 100	1098 ms	17912 KiB

ho_t5

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

long long S[200005];

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

int N;

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]);
    }

    init();

    for(int i = 1; i <= Q; i ++){
        int t, l, r;
        scanf("%d%d%d", &t, &l, &r);

        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:55: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:52: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:55: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:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &t, &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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