Submission #233751

#	Time	Username	Problem	Language	Result	Execution time	Memory
233751		duality	Fire (JOI20_ho_t5)	C++11	14 / 100	1090 ms	17656 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;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

int S[200000];
LLI pre[200001],pre2[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;
    int k = 0,f = 0;
    for (i = 0; i < Q; i++) {
        if ((i > 0) && (queries[i].T != queries[i-1].T)) f = 0;
        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;
        }
        int d = queries[i].T-c;
        while ((k < Q) && (queries[k].T == queries[i].T)) k++;
        if (!f && (k-i > 10)) {
            f = 1;
            for (j = 0; j < N; j++) pre2[j+1] = pre2[j]+max(S[j],(j >= d) ? S[j-d]:0);
        }
        if (f) ans[queries[i].i] = pre2[queries[i].R+1]-pre2[queries[i].L];
        else {
            LLI a = 0;
            if (d > queries[i].L) a += pre[min(d,queries[i].R+1)]-pre[queries[i].L];
            int e = max(d,queries[i].L);
            if (e <= queries[i].R) {
                int *p = S+e,*q = S+(e-d);
                int t = queries[i].R-e+1;
                for (j = 0; j < t; j++) {
                    a += (*p > *q) ? *p:*q;
                    p++,q++;
                }
                //for (j = e; j <= queries[i].R; 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:23: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:24: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:26: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: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80