Submission #1180017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180017		omarrrr	Fire (JOI20_ho_t5)	C++20	1 / 100	1094 ms	12184 KiB

ho_t5

#include<bits/stdc++.h>
#define ll long long
#define S second
#define F first
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    ll n,q,a,b,t;
    cin>>n>>q;
    vector<ll>s(n),x(n);
    for(ll i=0;i<n;i++){
        cin>>s[i];
    }


    ll pref[n+5];


    while(q--){
        cin>>t>>a>>b;
        priority_queue<pair<ll,ll>>mx;
        mx.push({s[0],0});
        for(ll i=1;i<n;i++){
            mx.push({s[i],i});
            while(i-mx.top().S>=t+1){
                mx.pop();
            }
            x[i]=mx.top().F;
        }
        x[0]=s[0];
//        for(ll j:x){
//            cout<<j<<" ";
//        }
        pref[0]=0;
        for(ll i=0;i<n;i++){
            pref[i+1]=pref[i]+x[i];
//        cout<<pref[i+1]<<" ";
        }
        a--;
        cout<<pref[b]-pref[a]<<"\n";
    }

    return 0;
}
/*
 5 5
 9 3 2 6 5
 3 2 2
 3 1 5
 3 3 5
 3 2 5
 3 2 4

 */

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