Submission #242645

#	Time	Username	Problem	Language	Result	Execution time	Memory
242645		lyc	Triple Jump (JOI19_jumps)	C++14	32 / 100	258 ms	28908 KiB

jumps

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

const int mxN = 5e5+5;
const int mxQ = 5e5+5;
const int INF = 1e9;

int N, A[mxN], Q, L[mxQ], R[mxQ];
int qid[mxQ], ans[mxQ];
vector<int> gb[mxN];

struct SegmentTree {
    struct node {
        int ab, c, abc, tagab;
    } D[mxN*4];
    int L, R;
    SegmentTree(int L, int R): L(L), R(R) { build(1,L,R); }

    void build(int p, int s, int e) {
        if (s == e) D[p] = { -INF, A[s], -INF, 0 };
        else {
            int m = (s+e)/2;
            build(p*2,s,m), build(p*2+1,m+1,e);
            D[p].c = max(D[p*2].c,D[p*2+1].c);
        }
    }

    void pushdown(int p, int s, int e) {
        if (!D[p].tagab) return;
        D[p].ab = max(D[p].ab,D[p].tagab);
        D[p].abc = max(D[p].abc,D[p].ab+D[p].c);
        if (s != e) {
            D[p*2].tagab = max(D[p*2].tagab,D[p].tagab);
            D[p*2+1].tagab = max(D[p*2+1].tagab,D[p].tagab);
        }
        D[p].tagab = 0;
    }

    void update(int p, int s, int e, int x, int y, int v) {
        if (s == x && e == y) {
            D[p].tagab = max(D[p].tagab,v);
        } else {
            int m = (s+e)/2;
            if (y <= m) update(p*2,s,m,x,y,v);
            else if (x > m ) update(p*2+1,m+1,e,x,y,v);
            else update(p*2,s,m,x,m,v), update(p*2+1,m+1,e,m+1,y,v);
            pushdown(p,s,e);
            pushdown(p*2,s,m);
            pushdown(p*2+1,m+1,e);
            D[p].abc = max(D[p*2].abc,D[p*2+1].abc);
        }
    }
    void update(int x, int y, int v) { return update(1,L,R,x,y,v); }

    int query(int p, int s, int e, int x, int y) {
        pushdown(p,s,e);
        if (s == x && e == y) return D[p].abc;
        else {
            int m = (s+e)/2;
            if (y <= m) return query(p*2,s,m,x,y);
            else if (x > m) return query(p*2+1,m+1,e,x,y);
            else return max(query(p*2,s,m,x,m),query(p*2+1,m+1,e,m+1,y));
        }
    }
    int query(int x, int y) { return query(1,L,R,x,y); }
} *root;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    FOR(i,1,N){
        cin >> A[i];
    }
    cin >> Q;
    FOR(i,1,Q){
        cin >> L[i] >> R[i];
        qid[i] = i;
    }

    vector<int> stk;
    FOR(i,1,N){
        while (!stk.empty() && A[i] > A[stk.back()]) {
            gb[stk.back()].push_back(i);
            stk.pop_back();
        }
        if (!stk.empty()) gb[stk.back()].push_back(i);
        stk.push_back(i);
    }
    sort(qid+1,qid+1+N,[](int i, int j){ return L[i] == L[j] ? i < j : L[i] > L[j]; });
    root = new SegmentTree(1,N);
    int a = N;
    FOR(i,1,Q){
        int q = qid[i];
        for (; a >= L[q]; --a) {
            for (int b : gb[a]) {
                if (b+(b-a) <= N) root->update(b+(b-a), N, A[a]+A[b]);
            }
        }
        ans[q] = root->query(L[q],R[q]);
    }
    FOR(i,1,Q){
        cout << ans[i] << '\n';
    }
}

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