Submission #1098631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098631		flyingkite	Triple Jump (JOI19_jumps)	C++17	100 / 100	1127 ms	145624 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 5e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,q;
ll a[N], nxt[N], res[N];
vector<ll>candi[N];
vector<pll>t[N];
struct segment_tree{
    ll n;
    vector<ll>st, lz, mx, val;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
        lz.clear(); lz.resize(4 * n + 10, 0);
        mx.clear(); mx.resize(4 * n + 10);
        val.clear(); val.resize(4 * n + 10);
        build(1,1,n);
    }
    void build(ll id, ll l, ll r){
        st[id] = -inf;
        val[id] = -inf;
        if(l == r){
            mx[id] = a[l];
            return;
        }
        ll mid = (l + r) / 2;
        build(2 * id, l, mid); build(2 * id + 1, mid + 1, r);
        mx[id] = max(mx[2 * id], mx[2 * id + 1]);
    }
    void down(ll id, ll l, ll r){
        st[id] = max(lz[id], st[id]);
        val[id] = max(val[id], mx[id] + st[id]);
        if(l != r) lz[2 * id] = max(lz[2 * id], lz[id]), lz[2 * id + 1] = max(lz[2 * id + 1], lz[id]);
        lz[id] = 0;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll v){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] = max(lz[id], v);
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, v);
        update(2 * id + 1, mid + 1, r, left, right, v);
        val[id] = max(val[2 * id], val[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return -inf;
        if(left <= l && r <= right) return val[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} st;
void to_thic_cau(){
    cin >> n;
    for(int i = 1; i <= n;i++) cin >> a[i];
    a[n+1] = a[0] = inf;
    stack<ll>s;
    s.push(n + 1);
    for(int i = n; i >= 1;i--){
        while(a[s.top()] < a[i]) s.pop();
        if(s.top() <= n) candi[i].pb(s.top());
        s.push(i);
    }
    while(s.size()) s.pop();
    s.push(0);
    for(int i = 1; i <= n;i++){
        while(a[s.top()] < a[i]) s.pop();
        if(s.top() >= 1) candi[s.top()].pb(i);
        s.push(i);
    }
    cin >> q;
    for(int i = 1; i <= q;i++){
        ll l,r; cin >> l >> r;
        t[l].pb({r, i});
    }
    st.init(n);
    for(int i = n; i >= 1;i--){
        for(auto x : candi[i]){
            ll len = x - i;
            if(x + len <= n) st.update(x + len, n, a[i] + a[x]);
        }
        for(auto x : t[i]) res[x.S] = st.get(i, x.F);
    }
    for(int i = 1; i <= q;i++) cout << res[i] << '\n';
}
 
signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

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