Submission #1276990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276990		phamminhson	Fire (JOI20_ho_t5)	C++20	0 / 100	354 ms	327680 KiB

ho_t5

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 2000005;
int N,Q;
ll S[MAXN];
int ng[MAXN];
int st[MAXN],top;
int Lq[MAXN],Rq[MAXN],Tq[MAXN],idq[MAXN];
ll diffA[MAXN],valA[MAXN],prefA[MAXN],ans[MAXN];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if(!(cin>>N)) return 0;
    for(int i=1;i<=N;i++) cin>>S[i];
    top=0;
    for(int i=N;i>=1;i--){
        while(top>0 && S[st[top-1]]<=S[i]) top--;
        if(top==0) ng[i]=N+1; else ng[i]=st[top-1];
        st[top++]=i;
    }
    cin>>Q;
    for(int i=0;i<Q;i++){
        cin>>Lq[i]>>Rq[i]>>Tq[i];
        idq[i]=i;
    }
    unordered_map<int, vector<int>> mp;
    mp.reserve(Q*2+10);
    for(int i=0;i<Q;i++) mp[Tq[i]].push_back(i);
    for(auto &pr: mp){
        int T = pr.first;
        if(T> N) T = N;
        int t = T;
        for(int i=1;i<=N+1;i++) diffA[i]=0;
        for(int j=1;j<=N;j++){
            int r = j + t;
            if(r > N) r = N;
            int ngpos = ng[j]-1;
            if(ngpos < r) r = ngpos;
            if(r >= j){
                diffA[j] += S[j];
                diffA[r+1] -= S[j];
            }
        }
        ll cur=0;
        for(int i=1;i<=N;i++){
            cur += diffA[i];
            valA[i]=cur;
            prefA[i]=prefA[i-1]+valA[i];
        }
        for(int idx: pr.second){
            int L=Lq[idx], R=Rq[idx];
            ans[idq[idx]] = prefA[R] - prefA[L-1];
        }
        for(int i=0;i<=N;i++) prefA[i]=0;
    }
    for(int i=0;i<Q;i++) cout<<ans[i]<<"\n";
    return 0;
}

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