Submission #946865

#	Time	Username	Problem	Language	Result	Execution time	Memory
946865		hmm789	Triple Jump (JOI19_jumps)	C++14	100 / 100	917 ms	130716 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007

struct node {
    int s, e, m, ab, c, abc, lz;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2, ab = c = abc = 0, lz = -1;
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
        }
    }
    void prop() {
        if(lz == -1) return;
        ab = max(ab, lz);
        abc = max(abc, ab+c);
        if(s != e) {
            l->lz = max(l->lz, lz);
            r->lz = max(r->lz, lz);
        }
        lz = -1;
    }
    void update(int x, int y, int val) {
        if(x > y) return;
        prop();
        if(x <= s && e <= y) {lz = max(val, lz); return;}
        else if(x > m) r->update(x, y, val);
        else if(y <= m) l->update(x, y, val);
        else l->update(x, y, val), r->update(x, y, val);
        l->prop(); r->prop();
        abc = max(l->abc, r->abc);
    }
    void update2(int x, int val) {
        if(s == e) {c = val; return;}
        else if(x > m) r->update2(x, val);
        else l->update2(x, val);
        c = max(l->c, r->c);
    }
    int rmax(int x, int y) {
        if(x > y) return -INF;
        prop();
        if(x <= s && e <= y) return abc;
        else if(x > m) return r->rmax(x, y);
        else if(y <= m) return l->rmax(x, y);
        else return max(l->rmax(x, y), r->rmax(x, y));
    }
} *root, *root2;

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q, x, y, idx;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];
    cin >> q;
    tuple<int, int, int> qry[q];
    int ans[q];
    for(int i = 0; i < q; i++) {
        cin >> x >> y;
        x--; y--;
        qry[i] = {x, y, i};
    }
    sort(qry, qry+q);
    stack<int> s;
    vector<pair<int, int>> good;
    for(int i = 0; i < n; i++) {
        while(s.size() && a[s.top()] <= a[i]) {
            good.push_back({s.top(), i});
            s.pop();
        }
        if(s.size()) good.push_back({s.top(), i});
        s.push(i);
    }
    sort(good.begin(), good.end());
    int gidx = good.size()-1, qidx = q-1;
    root = new node(0, n-1);
    for(int i = 0; i < n; i++) root->update2(i, a[i]);
    for(int i = n-1; i >= 0; i--) {
        while(gidx >= 0 && good[gidx].first == i) {
            root->update(min(2*good[gidx].second-good[gidx].first, n), n-1, a[good[gidx].first] + a[good[gidx].second]);
            gidx--;
        }
        while(qidx >= 0 && get<0>(qry[qidx]) == i) {
            tie(x, y, idx) = qry[qidx];
            ans[idx] = root->rmax(x, y);
            qidx--;
        }
    }
    for(int i = 0; i < q; i++) cout << ans[i] << '\n';
}

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