Submission #1134794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134794		dombly	Triple Jump (JOI19_jumps)	C++20	0 / 100	148 ms	51228 KiB

jumps

#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
const int N = 5e5 + 10;
const int inf = 1e15;
const int mod = 1e9 + 7;

vector<pair<int,int>>kveri[N],upd[N];
int ans[N],lazy[N * 4],a[N];

struct cvor {
    int mx,ans,lazy;
};

cvor st[N * 4];

void build(int node,int tl,int tr) {
    if(tl == tr) {
        st[node].ans = a[tl];
        st[node].mx = a[tl];
        st[node].lazy = 0;
        return;
    }
    int mid = (tl + tr) / 2;
    build(node * 2,tl,mid);
    build(node * 2 + 1,mid + 1,tr);
    st[node].ans = max(st[node * 2].ans,st[node * 2 + 1].ans);
    st[node].mx = max(st[node * 2].mx,st[node * 2 + 1].mx);
    st[node].lazy = 0;
}

void push(int node,int tl,int tr) {
    st[node].ans = max(st[node].ans,st[node].lazy + st[node].mx);
    if(tl != tr) {
        st[node * 2].lazy = max(st[node * 2].lazy,st[node].lazy);
        st[node * 2 + 1].lazy = max(st[node * 2 + 1].lazy,st[node].lazy);
    }
    st[node].lazy = 0;
}

void modify(int node,int tl,int tr,int l,int r,int v) {
    push(node,tl,tr);
    if(tl > r || tr < l || l > r) return;
    if(tl >= l && tr <= r) {
        st[node].lazy = v;
        push(node,tl,tr);
        return;
    }
    int mid = (tl + tr) / 2;
    modify(node * 2,tl,mid,l,r,v);
    modify(node * 2 + 1,mid + 1,tr,l,r,v);
    st[node].ans = max(st[node * 2].ans,st[node * 2 + 1].ans);
    st[node].mx = max(st[node * 2].mx,st[node * 2 + 1].mx);
}

int get(int node,int tl,int tr,int l,int r) {
    push(node,tl,tr);
    if(tl > r || tr < l || l > r) return 0;
    if(tl >= l && tr <= r) return st[node].ans;
    int mid = (tl + tr) / 2;
    return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,q;
    cin >> n;
    vector<int> l(n + 1),r(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1,1,n);
    stack<int>st;
    for(int i = 1; i <= n; i++) {
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        l[i] = (st.empty() ? -1 : st.top());
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n; i >= 1; i--) {
        while(!st.empty() && a[st.top()] <= a[i]) st.pop();
        r[i] = (st.empty() ? n + 1 : st.top());
        st.push(i);
    }
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int ll,rr;
        cin >> ll >> rr;
        kveri[ll].pb({rr,i});
    }
    for(int i = 1; i <= n; i++) {
        if(l[i] != -1 && 2 * i - l[i] <= n) upd[l[i]].pb({2 * i - l[i],a[i] + a[l[i]]});
        if(r[i] != n + 1 && 2 * r[i] - i <= n) upd[i].pb({2 * r[i] - i,a[i] + a[r[i]]});
    }
    for(int i = n; i >= 1; i--) {
        for(auto X : upd[i]) modify(1,1,n,X.F,n,X.S);
        for(auto X : kveri[i]) {
            ans[X.S] = get(1,1,n,i,X.F);
        }
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
    return 0;
}

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