Submission #1012861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012861		fryingduc	Triple Jump (JOI19_jumps)	C++17	100 / 100	509 ms	57772 KiB

jumps

#include "bits/stdc++.h"
using namespace std;

const int maxn = 5e5 + 5;

const int inf = 1e9;

int n, q, a[maxn];
vector<pair<int, int>> cand;
int ans[maxn];

struct node {
    int res, ft, se;
    node() {
        res = ft = se = 0;
    }
    node(int x, int y, int z) : res(x), ft(y), se(z) {}
    node operator+(const node &o) const {
        node tmp = *this;
        tmp.res = max({tmp.res, o.res, this->ft + o.se});
        tmp.se = max(tmp.se, o.se);
        tmp.ft = max(tmp.ft, o.ft);
        return tmp;
    }
} tree[maxn * 4];
struct segment_tree {
    int n;
    segment_tree() {}
    segment_tree(int n) : n(n) {}
    void build(int ind, int l, int r) {
        if(l == r) {
            tree[ind].res = tree[ind].se = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(ind * 2, l, mid);
        build(ind * 2 + 1, mid + 1, r);
        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
    }
    void update(int ind, int l, int r, int pos, int val) {
        if(l == r) {
            tree[ind].ft = max(tree[ind].ft, val);
            tree[ind].res = tree[ind].ft + tree[ind].se;
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid) update(ind * 2, l, mid, pos, val);
        else update(ind * 2 + 1, mid + 1, r, pos, val);
        tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
    }
    node get(int ind, int l, int r, int x, int y) {
        if(l > y || r < x) return node();
        if(x <= l and r <= y) return tree[ind];
        int mid = (l + r) / 2;
        return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
    }
    void update(int pos, int val) {
        update(1, 1, n, pos, val);
    }
    node get(int x, int y) {
        return get(1, 1, n, x, y);
    }
} st;
struct query {
    int l, r, id;
    bool operator<(const query &o) {
        return l > o.l;
    }
} que[maxn];
void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    stack<int> s;
    for(int i = 1; i <= n; ++i) {
        while(!s.empty() and a[i] >= a[s.top()]) {
            cand.push_back({s.top(), i * 2 - s.top()});
            s.pop();
        }
        if(!s.empty()) {
            cand.push_back({s.top(), i * 2 - s.top()});
        }        
        s.push(i);
    }
    st = segment_tree(n);
    st.build(1, 1, n);
    cin >> q;
    for(int i = 1; i <= q; ++i) {
        cin >> que[i].l >> que[i].r;
        que[i].id = i;
    }
    sort(que + 1, que + q + 1);
    sort(cand.begin(), cand.end(), [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
        return x.first > y.first;
    });
    int j = 0;
    for(int i = 1; i <= q; ++i) {
        while(j < (int)cand.size() and cand[j].first >= que[i].l) {
            int x = cand[j].first, y = cand[j].second;
            int z = (y + x) / 2;
            if(y <= n) st.update(y, a[x] + a[z]);
            ++j;
//            cerr << x << " " << z << " " << y << '\n';
        }
        ans[que[i].id] = st.get(que[i].l, que[i].r).res;
    }
    for(int i = 1; i <= q; ++i) {
        cout << ans[i] << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

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