Submission #349075

#	Time	Username	Problem	Language	Result	Execution time	Memory
349075		Vanjanja	Triple Jump (JOI19_jumps)	C++14	46 / 100	2075 ms	49708 KiB

jumps

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

const int N = 500005;
int a[N];
vector<pair<int, int>> que[N];
int resenje[N];
int b[N];
pair<int, int> c[N];
int seg[2 * N - 1][2];
int lazy[2 * N - 1];
int n;
int ind = 0;

void build(int u, int l, int r) {
    if (l == r) {
        seg[u][1] = a[l];
        return;
    }
    int mid  = (l + r) >> 1;
    build(u * 2 + 1, l, mid);
    build(u * 2 + 2, mid + 1, r);
    seg[u][1] = max(seg[u * 2 + 1][1], seg[u * 2 + 2][1]);
}

void upd(int u, int x) {
    seg[u][0] = max(seg[u][0], x + seg[u][1]);
    lazy[u] = max(lazy[u], x);
}

void shift(int u) {
    if (!lazy[u])
        return;
    upd(u * 2 + 1, lazy[u]);
    upd(u * 2 + 2, lazy[u]);
    lazy[u] = 0;
}

void update(int u, int l, int r, int L, int R, int x) {
    if (r < L || l > R)
        return;
    if (l >= L && r <= R) {
        upd(u, x);
        return;
    }
    shift(u);
    int mid = (l + r) >> 1;
    update(u * 2 + 1, l, mid, L, R, x);
    update(u * 2 + 2, mid + 1, r, L, R, x);
    seg[u][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 2][0]);
}

void Update(int i) {
    if (b[i]) {
        int l = 2 * b[i] - i;
        if (l < n) {
            update(0, 0, n - 1, l, n - 1, a[i] + a[b[i]]);
        }
    }
    while (c[ind].first == i) {
        int l = 2 * c[ind].second - c[ind].first;
        if (l < n) {
            update(0, 0, n - 1, l, n - 1, a[c[ind].first] + a[c[ind].second]);
        }
        ind++;
    }
}

int out(int u, int l, int r, int L, int R) {
    if (r < L || l > R)
        return 0;
    if (l >= L && r <= R) {
        return seg[u][0];
    }
    shift(u);
    int mid = (l + r) >> 1;
    return max(out(u * 2 + 1, l, mid, L, R), out(u * 2 + 2, mid + 1, r, L, R));
}

void veca(int n) {
    stack<int> s;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            b[s.top()] = i;
            s.pop();
        }
        s.push(i);
    }
}

void veca1(int n) {
    stack<int> s;
    for (int i = n - 1; i >= 0; i--) {
        while (!s.empty() && a[s.top()] <= a[i]) {
            c[ind].first = i;
            c[ind++].second = s.top();
            s.pop();
        }
        s.push(i);
    }
    c[ind].first = -1;
    ind = 0;
}

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    return a.first.first >= b.first.first;
}

void solve() {
    int q;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cin >> q;
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        que[l - 1].push_back({r - 1, i});
    }
    veca(n);
    veca1(n);
    build(0, 0, n - 1);
    for (int i = n - 1; i >= 0; i--) {
        Update(i);
        for (auto j = que[i].begin(); j != que[i].end(); j++) {
            pair<int, int> par = *j;
            resenje[par.second] = out(0, 0, n - 1, i, par.first);
        }
    }
    for (int i = 0; i < q; i++)
        cout << resenje[i] << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

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