Submission #233747

#	Time	Username	Problem	Language	Result	Execution time	Memory
233747		duality	Fire (JOI20_ho_t5)	C++11	0 / 100	1095 ms	15096 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

int S[200000];
LLI pre[200001];
struct query { int T,L,R,i; };
bool comp(query a,query b) {
    return a.T < b.T;
}
query queries[200000];
LLI ans[200000];
int main() {
    int i;
    int N,Q,T,L,R;
    scanf("%d %d",&N,&Q);
    for (i = 0; i < N; i++) scanf("%d",&S[i]);
    for (i = 0; i < Q; i++) {
        scanf("%d %d %d",&T,&L,&R);
        queries[i] = (query){T+1,L-1,R-1,i};
    }
    sort(queries,queries+Q,comp);

    int j,c = 1;
    for (i = 0; i < Q; i++) {
        while (queries[i].T >= 2*c) {
            for (j = N-1; j >= c; j--) S[j] = max(S[j],S[j-c]);
            for (j = 0; j < N; j++) pre[j+1] = pre[j]+S[j];
            c *= 2;
        }
        LLI a = 0;
        int d = queries[i].T-c;
        if (d > queries[i].L) a += pre[d]-pre[queries[i].L];
        int e = max(d,queries[i].L);
        for (j = queries[i].R; j >= e; j--) {
            a += max(S[j],S[j-d]);
        }
        ans[queries[i].i] = a;
    }
    for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);

    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:21: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:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&S[i]);
                             ~~~~~^~~~~~~~~~~~
ho_t5.cpp:24: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: 0 / 1
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80