Submission #993557

#	Time	Username	Problem	Language	Result	Execution time	Memory
993557		imarn	Triple Jump (JOI19_jumps)	C++14	46 / 100	242 ms	30128 KiB

jumps

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int mxn=3e5+5;
int a[mxn];
struct node{
    int mx,mxf,mxa;
    node operator+(node b){
        node rs;
        rs.mx=max({mx,b.mx,mxf+b.mxa});
        rs.mxf=max(mxf,b.mxf);
        rs.mxa=max(mxa,b.mxa);
        return rs;
    }
}t[4*mxn];
void build(int i,int l,int r){
    if(l==r)return void(t[i]={0,0,a[l]});
    int m=(l+r)>>1;build(2*i,l,m);build(2*i+1,m+1,r);
    t[i]=t[2*i]+t[2*i+1];
}
void update(int i,int l,int r,int idx,int v){
    if(r<idx||l>idx)return;
    if(l==r){
        t[i].mxf=max(t[i].mxf,v);
        t[i].mx=t[i].mxf+t[i].mxa;
        return;
    }int m=(l+r)>>1;update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
    t[i]=t[2*i]+t[2*i+1];
}
node query(int i,int l,int r,int tl,int tr){
    if(r<tl||l>tr)return {0,0,0};
    if(r<=tr&&l>=tl)return t[i];
    int m=(l+r)>>1;
    return query(2*i,l,m,tl,tr)+query(2*i+1,m+1,r,tl,tr);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    stack<int>st;vector<pii>gd;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[st.top()]<=a[i])gd.pb({st.top(),i}),st.pop();
        if(!st.empty())gd.pb({st.top(),i});st.push(i);
    }int id=0;build(1,1,n);
    int q;cin>>q;int ans[q+1];
    vector<pii>qr[n+1];
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        qr[l].pb({r,i});
    }sort(gd.rbegin(),gd.rend());
    for(int l=n;l>=1;l--){
        while(id<gd.size()&&gd[id].f>=l){id++;
            int idx=gd[id-1].s*2-gd[id-1].f;
            if(idx>n){continue;}
            update(1,1,n,idx,a[gd[id-1].f]+a[gd[id-1].s]);
        }
        for(auto it : qr[l]){
            ans[it.s]=query(1,1,n,l,it.f).mx;
        }
    }for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:48:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |         if(!st.empty())gd.pb({st.top(),i});st.push(i);
      |         ^~
jumps.cpp:48:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |         if(!st.empty())gd.pb({st.top(),i});st.push(i);
      |                                            ^~
jumps.cpp:57:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(id<gd.size()&&gd[id].f>=l){id++;
      |               ~~^~~~~~~~~~

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