Submission #1142447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142447		Noproblem29	Triple Jump (JOI19_jumps)	C++20	100 / 100	815 ms	66656 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#ifndef BADGNU
#pragma GCC target("sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif
#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ll long long
#define int ll
#define ld long double
#define y1 cheza
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int N=5e5+100;
const int M=5001;
const int B=447;
const int mod=998244353;
const ll INF=1e18;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps=1e-6;
int n,q;
int a[N];
int ans[N];
vector<pair<int,int>>g[N];
pair<int,int>t[N*4];
int add[N*4];
pair<int,int> operator+(const pair<int,int>&x,const pair<int,int>&y){
    pair<int,int>res;
    res.first=max(x.first,y.first);
    res.second=max(x.second,y.second);
    return res;
}
void build(int v,int tl,int tr){
    add[v]=-INF;
    if(tl==tr){
        t[v]={0,a[tl]};
        return;
    }
    int mid=(tl+tr)>>1ll;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
    t[v]=t[v*2]+t[v*2+1];
}
void push(int v,int tl,int tr){
    if(tl!=tr){
        add[v*2]=max(add[v*2],add[v]);
        add[v*2+1]=max(add[v*2+1],add[v]);
    }
    t[v].first=max(t[v].first,t[v].second+add[v]);
    add[v]=-INF;
}
void upd(int v,int tl,int tr,int l,int r,int x){
    push(v,tl,tr);
    if(tl>r||tr<l)return;
    if(l<=tl&&tr<=r){
        add[v]=x;
        push(v,tl,tr);
        return;
    }
    int mid=(tl+tr)>>1ll;
    upd(v*2,tl,mid,l,r,x);
    upd(v*2+1,mid+1,tr,l,r,x);
    t[v]=t[v*2]+t[v*2+1];
}
int get(int v,int tl,int tr,int l,int r){
    push(v,tl,tr);
    if(tl>r||tr<l)return 0;
    if(l<=tl&&tr<=r)return t[v].first;
    int mid=(tl+tr)>>1ll;
    return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}
void test(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>q;
    for(int l,r,i=1;i<=q;i++){
        cin>>l>>r;
        g[l].push_back({r,i});
    }
    stack<int>s;
    build(1,1,n);
    for(int i=n;i>=1;i--){
        while(s.size()){
            int j=s.top();
            if(j*2-i<=n){
                upd(1,1,n,j*2-i,n,a[i]+a[j]);
            }
            if(a[i]<a[j])break;
            s.pop();
        }
        s.push(i);
        for(auto [r,pos]:g[i]){
            ans[pos]=get(1,1,n,i+2,r);
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<'\n';
    }
}



/*

*/
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.tie(nullptr);
    int t2=1;
    // cin>>t2;
    for(int i=1;i<=t2;i++){
        test();
    }
}

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