Submission #709349

#	Time	Username	Problem	Language	Result	Execution time	Memory
709349		snpmrnhlol	Triple Jump (JOI19_jumps)	C++17	27 / 100	223 ms	33940 KiB

jumps

#include <bits/stdc++.h>
//#define cin fin
//#define cout fout
using namespace std;
//ifstream cin("a.in");
//ofstream cout("a.out");
typedef long long ll;
const ll N = 500000;
ll v[N],v2[N],n;
struct query{
    ll l,r,id;
}v3[N];
ll ans[N];
bool cmp(query a,query b){
    return a.l < b.l;
}
tuple <ll,ll,ll> seg[4*N];
ll seg2[4*N];
tuple<ll,ll,ll> operator+(tuple<ll,ll,ll> &a,tuple<ll,ll,ll> &b){
    return {max(get<0>(a),get<0>(b)),max({get<1>(a),get<1>(b)}),0};
}
///1 2 -> normal,ans
///3 -> lazy max
void build(ll l,ll r,ll node = 1){
    if(l == r)seg[node] = {v[l],0,0};
    else{
        ll mij = (l + r)/2;
        build(l,mij,node*2);
        build(mij + 1,r,node*2 + 1);
        seg[node] = seg[node*2]+seg[node*2 + 1];
    }
};
void push(ll node,bool single){
    if(!get<2>(seg[node]))return;
    get<1>(seg[node]) = max(get<1>(seg[node]),get<0>(seg[node]) + get<2>(seg[node]));
    seg2[node] = max(seg2[node],get<2>(seg[node]));
    if(!single){
        get<2>(seg[node*2]) = max(get<2>(seg[node*2]),get<2>(seg[node]));
        get<2>(seg[node*2+1]) = max(get<2>(seg[node*2 + 1]),get<2>(seg[node]));
    }
    get<2>(seg[node]) = 0;
}
void upd(ll l,ll r,ll val,ll l2 = 0,ll r2 = n - 1,ll node = 1){
    //if(l2 == 0 && r2 == n - 1)cout<<l<<' '<<r<<' '<<val<<'\n';
    push(node,l==r);
    if(r2 < l || r < l2)return;
    if(l <= l2 && r2 <= r){
        get<2>(seg[node])+=val;
        push(node,l==r);
        //cout<<l2<<' '<<r2<<' '<<get<0>(seg[node])<<' '<<get<1>(seg[node])<<' '<<get<2>(seg[node])<<' '<<seg2[node]<<'\n';
    }else{
        ll mij = (l2 + r2)/2;
        upd(l,r,val,l2,mij,node*2);
        upd(l,r,val,mij + 1,r2,node*2 + 1);
        seg[node] = {max(get<0>(seg[node*2]),get<0>(seg[node*2+1])),max({get<1>(seg[node*2]),get<1>(seg[node*2+1]),get<0>(seg[node*2+1]) + seg2[node*2]}),0};
        seg2[node] = max(seg2[node*2],seg2[node*2 + 1]);
    }
}
ll bb = -2e9;
tuple <ll,ll,ll> query(ll l,ll r,ll l2 = 0,ll r2 = n - 1,ll node = 1){
    push(node,l==r);
    if(r2 < l || r < l2)return {-2e9,-2e9,0};
    if(l <= l2 && r2 <= r){
        //cout<<l2<<' '<<r2<<' '<<get<0>(seg[node])<<' '<<get<1>(seg[node])<<' '<<get<2>(seg[node])<<' '<<seg2[node]<<'\n';
        bb = max(bb,seg2[node]);
        return seg[node];
    }else{
        ll mij = (l2 + r2)/2;
        ll rb = bb;
        tuple<ll,ll,ll> l3 = query(l,r,l2,mij,node*2);
        tuple<ll,ll,ll> r3 = query(l,r,mij + 1,r2,node*2 + 1);
        return {max(get<0>(l3),get<0>(r3)),max(max(get<1>(l3),get<1>(r3)),get<0>(r3) + rb),0};
    }
}
int main(){
    ll q,i,cnt = -1,p,j;
    cin>>n;
    for(i = 0;i < n;i++){
        cin>>v[i];
    }
    cin>>q;
    for(i = 0;i < q;i++){
        cin>>v3[i].l>>v3[i].r;v3[i].id = i;
        v3[i].l--;v3[i].r--;
    }
    build(0,n - 1);
    sort(v3,v3 + q,cmp);
    p = q - 1;
    for(i = n - 1;i >= 0;i--){
        while(cnt >= 0 && v[i] >= v[v2[cnt]]){
            if(v2[cnt]*2 - i <= n - 1){
                upd(v2[cnt]*2 - i,n - 1,v[i] + v[v2[cnt]]);
            }
            cnt--;
        }
        if(cnt >= 0 && v2[cnt]*2 - i <= n - 1){
            upd(v2[cnt]*2 - i,n - 1,v[i] + v[v2[cnt]]);
        }
        while(p >= 0 && i == v3[p].l){
            bb = -2e9;
            ans[v3[p].id] = get<1>(query(v3[p].l,v3[p].r));
            p--;
        }
        if(p == -1)break;
        ///add
        v2[++cnt] = i;
    }
    for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:76:23: warning: unused variable 'j' [-Wunused-variable]
   76 |     ll q,i,cnt = -1,p,j;
      |                       ^

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