Submission #233755

#	Time	Username	Problem	Language	Result	Execution time	Memory
233755		duality	Fire (JOI20_ho_t5)	C++11	100 / 100	341 ms	49536 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 l[200000],depth[200000];
vi SS;
vpii events[200005];
LLI bit[200001];
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);

    LLI sum = 0;
    for (i = 0; i < N; i++) {
        while (!SS.empty() && (S[SS.back()] <= S[i])) SS.pop_back();
        if (SS.empty()) l[i] = -1,depth[i] = 0;
        else l[i] = SS.back(),depth[i] = depth[l[i]]+1;
        SS.pb(i),sum += depth[i];
    }
    if (sum <= 1e7) {
        for (i = 0; i < N; i++) {
            int u = i,p = 0;
            while (u != -1) {
                events[i-u+1].pb(mp(i,S[u]-p));
                p = S[u],u = l[u];
            }
        }
        int j = 0,k,l;
        for (i = 0; i < Q; i++) {
            while (j <= queries[i].T) {
                for (k = 0; k < events[j].size(); k++) {
                    for (l = events[j][k].first+1; l <= N; l += l & (-l)) bit[l] += events[j][k].second;
                }
                j++;
            }
            LLI a = 0;
            for (l = queries[i].R+1; l > 0; l -= l & (-l)) a += bit[l];
            for (l = queries[i].L; l > 0; l -= l & (-l)) a -= bit[l];
            ans[queries[i].i] = a;
        }
        for (i = 0; i < Q; i++) printf("%lld\n",ans[i]);
        return 0;
    }

    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;
                int tt = (t/4)*4;
                for (j = 0; j < tt; j += 4) {
                    a += (p[j] > q[j]) ? p[j]:q[j];
                    a += (p[j+1] > q[j+1]) ? p[j+1]:q[j+1];
                    a += (p[j+2] > q[j+2]) ? p[j+2]:q[j+2];
                    a += (p[j+3] > q[j+3]) ? p[j+3]:q[j+3];
                }
                for (; j < t; j++) a += (p[j] > q[j]) ? p[j]:q[j];
            }
            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:53:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (k = 0; k < events[j].size(); k++) {
                             ~~^~~~~~~~~~~~~~~~~~
ho_t5.cpp:27: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:28: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:30: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: 6 / 6
• Subtask 5: 80 / 80