제출 #1167582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167582		antonn	3단 점프 (JOI19_jumps)	C++20	0 / 100	142 ms	42420 KiB

jumps

#include <bits/stdc++.h> 

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 5e5 + 7;
const int inf = 1e9;

int x[N];
vector<int> add[N];
vector<pi> qs[N];

struct Node {
    int maxab;
    int maxc;
    int res;
};

Node operator + (Node a, Node b) {
    Node c;
    c.maxab = max(a.maxab, b.maxab);
    c.maxc = max(a.maxc, b.maxc);
    c.res = max(a.res, b.res);
    c.res = max(c.res, a.maxab + b.maxc);
    return c;
}

Node t[4 * N];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v].maxc = x[tl];
        t[v].maxab = -inf;
        t[v].res = -1e9;
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = t[2 * v] + t[2 * v + 1];
}

void change(int v, int tl, int tr, int p, int x) {
    if (tl > p || tr < p) return;
    if (tl == tr) {
        ckmax(t[v].maxab, x);
        t[v].res = t[v].maxab + t[v].maxc;
        return;
    } 
    int tm = (tl + tr) / 2;
    change(2 * v, tl, tm, p, x);
    change(2 * v + 1, tm + 1, tr, p, x);
    t[v] = t[2 * v] + t[2 * v + 1];
}

Node get(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return {-inf, -inf, -inf};
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return get(2 * v, tl, tm, l, r) + get(2 * v + 1, tm + 1, tr, l, r);
} 

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; cin >> n; 
    for (int i = 1; i <= n; ++i) cin >> x[i];
    
    vector<pi> ab;
    
    stack<int> stk;
    vector<int> nxt(n + 1); // nxt[i] = smallest index j such that a[j] > a[i]
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && x[stk.top()] <= x[i]) { // remove all element greater than A[i] from the stack 
            stk.pop();
        }
        if (!stk.empty()) {
            nxt[i] = stk.top(); 
        } else {
            nxt[i] = n + 1; // there is no greater element to the right of element i
        }
        stk.push(i); // add A[i] to the stack
    }
    while (!stk.empty()) { // clear the stack 
        stk.pop();
    }
    vector<int> prv(n + 1); // prv[i] = biggest index j such that a[j] > a[i]
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && x[stk.top()] <= x[i]) {
            stk.pop();
        }
        if (!stk.empty()) {
            prv[i] = stk.top(); 
        } else {
            prv[i] = 0; 
        }
        stk.push(i);
    }
    // now we can extract the desired pairs
    for (int i = 1; i <= n; ++i) {
        if (prv[i] != 0) {
            ab.push_back({prv[i], i});
        }
        if (nxt[i] != N + 1) {
            ab.push_back({i, nxt[i]});
        }
    }
    
    for (auto [a, b] : ab) add[a].push_back(b);
    
    int q; cin >> q; vector<int> sol(q + 1);
    for (int i = 1; i <= q; ++i) {
        int l, r; cin >> l >> r;
        qs[l].push_back({r, i});
    }
    build(1, 1, n);
    for (int l = n; l >= 1; --l) {
        for (auto b : add[l]) change(1, 1, n, 2 * b - l, x[l] + x[b]);
        for (auto [r, i] : qs[l]) sol[i] = get(1, 1, n, l, r).res;
    }
    for (int i = 1; i <= q; ++i) cout << sol[i] << "\n";
}

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