Submission #745576

#	Time	Username	Problem	Language	Result	Execution time	Memory
745576		Pacybwoah	Fire (JOI20_ho_t5)	C++14	6 / 100	171 ms	19916 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);
    vector<ll> pre(n+1);
    int a,b,c;
    cin>>a>>b>>c;
    for(int i=1;i<=n;i++){
        pre[i]=query(1,n,max(1,i-a),i,1);
    }
    for(int i=2;i<=n;i++) pre[i]+=pre[i-1];
    cout<<pre[c]-pre[b-1]<<"\n";
    for(int i=1;i<q;i++){
        cin>>a>>b>>c;
        cout<<pre[c]-pre[b-1]<<"\n";
    }
}

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