Submission #615827

#	Time	Username	Problem	Language	Result	Execution time	Memory
615827		AbdelmagedNour	Triple Jump (JOI19_jumps)	C++17	100 / 100	812 ms	46560 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
struct node{
    int res,f,mx;
    node(){res=f=mx=0;}
    node(int _res,int _f,int _mx){
        res=_res;
        f=_f;
        mx=_mx;
    }
};
struct SegTree{
    node tree[1<<20];
    int sz;
    node Merge(node&a,node&b){
        int res=max({a.res,b.res,a.f+b.mx}),f=max(a.f,b.f),mx=max(a.mx,b.mx);
        return node(res,f,mx);
    }
    void build(int l,int r,int p,vector<int>&a){
        if(l==r){
            tree[p].f=-1e9;
            tree[p].res=-1e9;
            tree[p].mx=0;
            if(l<a.size())tree[p].mx=a[l];
            return;
        }
        int md=(l+r)>>1;
        build(l,md,p*2+1,a);
        build(md+1,r,p*2+2,a);
        tree[p]=Merge(tree[p*2+1],tree[p*2+2]);
    }
    void init(int n,vector<int>&a){
        sz=1;
        while(sz<n)sz*=2;
        build(0,sz-1,0,a);
    }
    void update(int l,int r,int p,int idx,int f){
        if(l==r){
            tree[p].f=max(tree[p].f,f);
            tree[p].res=tree[p].f+tree[p].mx;
            return;
        }
        int md=(l+r)>>1;
        if(md>=idx)update(l,md,p*2+1,idx,f);
        else update(md+1,r,p*2+2,idx,f);
        tree[p]=Merge(tree[p*2+1],tree[p*2+2]);
    }
    void update(int idx,int f){
        update(0,sz-1,0,idx,f);
    }
    node query(int l,int r,int p,int l_q,int r_q){
        if(l>r_q||r<l_q)return node(0,0,0);
        if(l>=l_q&&r<=r_q)return tree[p];
        int md=(l+r)>>1;
        node ch1=query(l,md,p*2+1,l_q,r_q);
        node ch2=query(md+1,r,p*2+2,l_q,r_q);
        return Merge(ch1,ch2);
    }
    int query(int l,int r){
        return query(0,sz-1,0,l,r).res;
    }
}tree;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    vector<pair<int,int>>seg;
    vector<int>st;// decreasing stack
    for(int i=0;i<n;i++){
        while(!st.empty()&&a[i]>=a[st.back()]){
            seg.push_back({st.back(),i});
            st.pop_back();
        }
        if(!st.empty())seg.push_back({st.back(),i});
        st.push_back(i);
    }
    sort(seg.begin(),seg.end());
    tree.init(n,a);
    int q;
    cin>>q;
    int L[q],R[q],sorted[q],ans[q];
    for(int i=0;i<q;i++){
        cin>>L[i]>>R[i];
        L[i]--;R[i]--;
        sorted[i]=i;
    }
    sort(sorted,sorted+q,[&](int i,int j){
            return L[i]>L[j];
         });
    for(int i=0;i<q;i++){
        while(!seg.empty()&&seg.back().first>=L[sorted[i]]){
            auto[l,r]=seg.back();
            if(2*r-l<n)tree.update(2*r-l,a[l]+a[r]);
            seg.pop_back();
        }
        ans[sorted[i]]=tree.query(L[sorted[i]],R[sorted[i]]);
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
    return 0;
}

Compilation message (stderr)

jumps.cpp: In member function 'void SegTree::build(int, int, int, std::vector<int>&)':
jumps.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             if(l<a.size())tree[p].mx=a[l];
      |                ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54