Submission #258965

#	Time	Username	Problem	Language	Result	Execution time	Memory
258965		doowey	Triple Jump (JOI19_jumps)	C++14	100 / 100	1135 ms	104184 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 9;
const int M = (int)1e6 + 10;

vector<int> X[N];
vector<pii> Q[N];
ll A[N];
ll ans[N];

struct Node{
    ll sol;
    ll f1;
    ll f2;
};

Node T[M * 4 + 512];

Node unite(Node A, Node B){
    Node res;
    res.sol = max(A.sol, B.sol);
    res.sol = max(res.sol, A.f1 + B.f2);
    res.f1 = max(A.f1, B.f1);
    res.f2 = max(A.f2, B.f2);
    return res;
}

void upd(int node, int cl, int cr, int pos, ll i1, ll i2){
    if(cl == cr){
        T[node].f1=max(T[node].f1, i1);
        T[node].f2=max(T[node].f2, i2);
        T[node].sol=T[node].f1+T[node].f2;
        return ;
    }
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        upd(node * 2, cl, mid, pos, i1, i2);
    else
        upd(node * 2 + 1, mid + 1, cr, pos, i1, i2);
    T[node] = unite(T[node * 2], T[node * 2 + 1]);
}

Node qq(int node, int cl, int cr, int tl, int tr){
    if(cr < tl)
        return {0, 0, 0};
    if(cl > tr)
        return {0, 0, 0};
    if(cl >= tl && cr <= tr){
        return T[node];
    }
    int mid = (cl + cr) / 2;
    Node f1 = qq(node * 2, cl, mid, tl, tr);
    Node f2 = qq(node * 2 + 1, mid + 1, cr, tl, tr);
    return unite(f1, f2);
}

int main(){
    fastIO;
    int n, q;
    cin >> n;
    vector<int> ids;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
        while(!ids.empty() && A[i] > A[ids.back()]){
            X[ids.back()].push_back(i);
            ids.pop_back();
        }
        if(!ids.empty()){
            X[ids.back()].push_back(i);
        }
        ids.push_back(i);
    }
    cin >> q;
    int l, r;
    for(int i = 1; i <= q; i ++ ){
        cin >> l >>r;
        Q[l].push_back(mp(r, i));
    }
    int id;
    for(int r = n; r >= 1; r -- ){
        upd(1, 1, n, r, 0ll, A[r]);

        for(auto x : X[r]){
            id = (2 * x - r);
            if(id <= n)
                upd(1, 1, n, id, A[r] + A[x], 0ll);
        }

        for(auto v : Q[r]){
            Node qji = qq(1, 1, n, r, v.fi);
            ans[v.se] = qji.sol;
        }

    }
    for(int i = 1 ; i <= q; i ++ ){
        cout << ans[i] << "\n";
    }
    return 0;
}

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