Submission #348407

#	Time	Username	Problem	Language	Result	Execution time	Memory
348407		Vanjanja	Triple Jump (JOI19_jumps)	C++17	0 / 100	4046 ms	27884 KiB

jumps

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

const int N = 500001;
int a[N];
pair<pair<int, int>, int> que[N];
int resenje[N];
int b[N];
pair<int, int> c[N];
int seg[4 * N - 1][2];
int lazy[4 * 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) {
    lazy[u * 2 + 1] = lazy[u];
    lazy[u * 2 + 2] = lazy[u];
    seg[u * 2 + 1][0] = max(seg[u * 2 + 1][0], seg[u * 2 + 1][1] + lazy[u]);
    seg[u * 2 + 2][0] = max(seg[u * 2 + 2][0], seg[u * 2 + 2][1] + 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;
    }
    if (lazy[u])
        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 x, int y) {
    for (int i = y - 1; i >= x; i--) {
        if (b[i] != -1) {
            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 && ind < n) {
            int l = 2 * c[ind].second - c[ind].first;
            if (l < n) {
                update(0, 0, n - 1, l, n - 1, a[i] + 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];
    }
    if (lazy[u])
        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<pair<int, int>> s;
    s.push(make_pair(a[0], 0));
    for (int i = 1; i < n; i++) {
        pair<int, int> top = s.top();
        while (!s.empty() && top.first <= a[i]) {
            b[top.second] = i;
            s.pop();
            if (!s.empty())
                top = s.top();
        }
        s.push(make_pair(a[i], i));
    }
    while (!s.empty()) {
        pair<int, int> top = s.top();
        b[top.second] = -1;
        s.pop();
    }
}

bool cmp1(pair<int, int> x, pair<int, int> y) {
    if (x.first > y.first)
        return true;
    if (x.second < y.second)
        return true;
    return false;
}

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

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++) {
        cin >> que[i].first.first >> que[i].first.second;
        que[i].second = i;
    }
    veca(n);
    veca1(n);
    sort(que, que + q, cmp);
    build(0, 0, n - 1);
    for (int i = 0; i < q; i++) {
        if (i == 0)
            Update(que[i].first.first - 1, n);
        else
            Update(que[i].first.first - 1, que[i - 1].first.first - 1);
        resenje[que[i].second] = out(0, 0, n - 1, que[i].first.first - 1, que[i].first.second - 1);
    }
    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: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54