Submission #709335

#	Time	Username	Problem	Language	Result	Execution time	Memory
709335		snpmrnhlol	Triple Jump (JOI19_jumps)	C++17	27 / 100	228 ms	15800 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int v[200000],v2[200000],n;
struct query{
    int l,r,id;
}v3[200000];
int ans[200000];
bool cmp(query a,query b){
    return a.l < b.l;
}
tuple <int,int,int> seg[800000];
tuple<int,int,int> operator+(tuple<int,int,int> &a,tuple<int,int,int> &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(int l,int r,int node = 1){
    if(l == r)seg[node] = {v[l],0,0};
    else{
        int 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];
    }
    //cout<<l<<' '<<r<<' '<<node<<' '<<get<0>(seg[node])<<'\n';
};
void push(int node,bool single){
    if(!get<2>(seg[node]))return;
    //cout<<node<<' '<<get<0>(seg[node])<<' '<<get<2>(seg[node])<<' ';
    get<1>(seg[node]) = max(get<1>(seg[node]),get<0>(seg[node]) + get<2>(seg[node]));
    //cout<<get<1>(seg[node])<<'\n';
    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(int l,int r,int val,int l2 = 0,int r2 = n - 1,int 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){
        //cout<<l2<<' '<<r2<<'\n';
        get<2>(seg[node])+=val;
        push(node,l==r);
    }else{
        //cout<<l2<<' '<<r2<<'\n';
        int mij = (l2 + r2)/2;
        upd(l,r,val,l2,mij,node*2);
        upd(l,r,val,mij + 1,r2,node*2 + 1);
        seg[node] = seg[node*2] + seg[node*2 + 1];
    }
}
tuple <int,int,int> query(int l,int r,int l2 = 0,int r2 = n - 1,int node = 1){
    push(node,l==r);
    if(r2 < l || r < l2)return {-2e9,-2e9,0};
    if(l <= l2 && r2 <= r){
        return seg[node];
    }else{
        int mij = (l2 + r2)/2;
        tuple<int,int,int> l3 = query(l,r,l2,mij,node*2);
        tuple<int,int,int> r3 = query(l,r,mij + 1,r2,node*2 + 1);
        return l3+r3;
    }
}
int main(){
    int 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);
    /*for(j = 0;j < 4*n;j++){
        cout<<j<<' '<<get<0>(seg[j])<<' '<<get<1>(seg[j])<<' '<<get<2>(seg[j])<<'\n';
    }
    cout<<'\n';*/
    sort(v3,v3 + q,cmp);
    p = q - 1;
    for(i = n - 1;i >= 0;i--){
        while(cnt >= 0 && v[i] >= v[v2[cnt]]){
            //cout<<i<<' '<<v2[cnt]<<'\n';
            if(v2[cnt]*2 - i <= n - 1){
                upd(v2[cnt]*2 - i,n - 1,v[i] + v[v2[cnt]]);
                //cout<<v2[cnt]<<' '<<i<<'\n';
                /*for(j = 0;j < 4*n;j++){
                    cout<<j<<' '<<get<0>(seg[j])<<' '<<get<1>(seg[j])<<' '<<get<2>(seg[j])<<'\n';
                }
                cout<<'\n';*/
            }
            cnt--;
        }
        if(cnt >= 0 && v2[cnt]*2 - i <= n - 1){
            upd(v2[cnt]*2 - i,n - 1,v[i] + v[v2[cnt]]);
            //cout<<v2[cnt]<<' '<<i<<'\n';
            /*for(j = 0;j < 4*n;j++){
                cout<<j<<' '<<get<0>(seg[j])<<' '<<get<1>(seg[j])<<' '<<get<2>(seg[j])<<'\n';
            }
            cout<<'\n';*/
        }
        while(p >= 0 && i == v3[p].l){
            ans[v3[p].id] = get<1>(query(v3[p].l,v3[p].r));
            //cout<<v3[p].id<<'\n';
            p--;
        }
        ///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:67:24: warning: unused variable 'j' [-Wunused-variable]
   67 |     int q,i,cnt = -1,p,j;
      |                        ^

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