Submission #1215330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215330		JooDdae	Triple Jump (JOI19_jumps)	C++20	100 / 100	1502 ms	82192 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

int n, m, a[500500];
vector<int> v[500500];
ll t[2002002], lz[2002002], ans[500500];

void lazy_update(int node, int l, int r) {
    if(!lz[node]) return;
    t[node] += lz[node];
    if(l != r) lz[node*2] += lz[node], lz[node*2+1] += lz[node];
    lz[node] = 0;
}

void update(int nl, int nr, int val, int node = 1, int l = 1, int r = n) {
    lazy_update(node, l, r);
    if(nr < l || r < nl) return;
    if(nl <= l && r <= nr) {
        lz[node] += val;
        lazy_update(node, l, r);
        return;
    }
    update(nl, nr, val, node*2, l, mid), update(nl, nr, val, node*2+1, mid+1, r);
    t[node] = max(t[node*2], t[node*2+1]);
}

ll find(int nl, int nr, int node = 1, int l = 1, int r = n) {
    lazy_update(node, l, r);
    if(nl > nr || nr < l || r < nl) return 0;
    if(nl <= l && r <= nr) return t[node];
    return max(find(nl, nr, node*2, l, mid), find(nl, nr, node*2+1, mid+1, r));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;

    vector<int> st;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        while(!st.empty()) {
            v[st.back()].push_back(i);
            if(a[st.back()] > a[i]) break;
            st.pop_back();
        }
        st.push_back(i);
    }

    cin >> m;
    vector<array<int, 3>> q(m);
    for(int i=0;i<m;i++) cin >> q[i][0] >> q[i][1], q[i][2] = i+1;
    sort(q.rbegin(), q.rend());

    set<pair<int, int>> s = {{0, 0}, {n+1, 2e9+10}};
    for(int i=n, j=0;i>=1;i--) {
        update(i, i, a[i]);

        for(auto r : v[i]) {
            int R = r+r-i, V = a[i]+a[r];
            if(R > n) continue;
            auto it = s.lower_bound({R+1, 0});
            if(prev(it)->second >= V) continue; 
            update(R, it->first-1, V-prev(it)->second);
            while(it->second <= V) {
                update(it->first, next(it)->first-1, V-it->second);
                it = s.erase(it);
            }
            s.insert({R, V});
        }
        while(j < m && q[j][0] == i) ans[q[j][2]] = find(next(s.begin())->first, q[j][1]), j++;
    }

    for(int i=1;i<=m;i++) cout << ans[i] << "\n";
}

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