Submission #745577

#	Time	Username	Problem	Language	Result	Execution time	Memory
745577		Pacybwoah	Fire (JOI20_ho_t5)	C++14	8 / 100	1075 ms	11756 KiB

ho_t5

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#define ll long long
using namespace std;
vector<ll> seg;
vector<ll> vec;
void build(int l,int r,int ind){
    if(l==r){
        seg[ind]=vec[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ind*2);
    build(mid+1,r,ind*2+1);
    seg[ind]=max(seg[ind*2],seg[ind*2+1]);
}
ll query(int l,int r,int start,int end,int ind){
    if(r<start||end<l) return 0;
    if(start<=l&&r<=end) return seg[ind];
    int mid=(l+r)>>1;
    return max(query(l,mid,start,end,ind*2),query(mid+1,r,start,end,ind*2+1));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    vector<ll> f(n+1);
    seg.resize(4*n+4);
    for(int i=0;i<n;i++) cin>>f[i+1];
    vec.resize(n+1);
    for(int i=1;i<=n;i++) vec[i]=f[i];
    build(1,n,1);
    int a,b,c;
    for(int i=0;i<q;i++){
        cin>>a>>b>>c;
        ll ans=0;
        for(int j=b;j<=c;j++){
            ans+=query(1,n,max(1,j-a),j,1);
        }
        cout<<ans<<"\n";
    }
}

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