Submission #490695

#	Time	Username	Problem	Language	Result	Execution time	Memory
490695		jhnah917	Triple Jump (JOI19_jumps)	C++14	100 / 100	591 ms	91416 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 19;

struct Node{
    int a, b, v;
    Node(){ a = b = v = 0; }
    Node(int a, int b, int v) : a(a), b(b), v(v) {}
    friend Node operator + (const Node &l, const Node &r){
        return { max(l.a, r.a), max(l.b, r.b), max({ l.v, r.v, l.a + r.b }) };
    }
} T[SZ << 1];

int N, Q, A[SZ], R[SZ];
vector<pair<int,int>> Upd[SZ], Qry[SZ];

void Init(){
    for(int i=0; i<SZ; i++) T[i|SZ].b = T[i|SZ].v = A[i];
    for(int i=SZ-1; i; i--) T[i] = T[i<<1] + T[i<<1|1];
}

void Update(int x, int v){
    x |= SZ;
    T[x].a = max(T[x].a, v);
    T[x].v = T[x].a + T[x].b;
    while(x >>= 1) T[x] = T[x<<1] + T[x<<1|1];
}

int Query(int l, int r){
    Node lv, rv; l |= SZ; r |= SZ;
    while(l <= r){
        if(l & 1) lv = lv + T[l++];
        if(~r & 1) rv = T[r--] + rv;
        l >>= 1; r >>= 1;
    }
    return (lv + rv).v;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    cin >> Q;
    for(int i=1,l,r; i<=Q; i++) cin >> l >> r, Qry[l].emplace_back(r, i);

    Init();
    stack<int> S;
    for(int i=1; i<=N; i++){
        while(!S.empty()){
            int j = S.top();
            Upd[j].emplace_back(i, A[i] + A[j]);
            if(A[i] <= A[j]) break;
            S.pop();
        }
        S.push(i);
    }

    for(int i=N; i>=1; i--){
        for(auto [idx,val] : Upd[i]) if(2*idx - i <= N) Update(2*idx - i, val);
        for(auto [end,idx] : Qry[i]) R[idx] = Query(i, end);
    }
    for(int i=1; i<=Q; i++) cout << R[i] << "\n";
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for(auto [idx,val] : Upd[i]) if(2*idx - i <= N) Update(2*idx - i, val);
      |                  ^
jumps.cpp:60:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for(auto [end,idx] : Qry[i]) R[idx] = Query(i, end);
      |                  ^

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