Submission #1180024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180024		omarrrr	Fire (JOI20_ho_t5)	C++20	7 / 100	81 ms	11184 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];
    }

    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];
    ll pref[n+5];
    pref[0]=0;
    for(ll i=0;i<n;i++){
        pref[i+1]=pref[i]+x[i];
//        cout<<pref[i+1]<<" ";
    }

    cout<<pref[b]-pref[a-1]<<"\n";
    q--;

    while(q--){
        cin>>t>>a>>b;
        if(n<=200 && q<=200){
            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: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 6
• Subtask 5: 0 / 80