Submission #137213

#	Time	Username	Problem	Language	Result	Execution time	Memory
137213		Minnakhmetov	Triple Jump (JOI19_jumps)	C++14	100 / 100	1423 ms	111988 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 5e5 + 5, INF = 1e9;
int a[N], lm[N], rm[N], t[N * 4], up[N * 4], ans[N], mx[N * 4];
vector<pair<int, int>> ev[N], qr[N];
bool tup[N * 4];

void build(int v, int L, int R) {
    if (L == R) {
        mx[v] = a[L];
    }
    else {
        int m = (L + R) >> 1;
        build(v * 2, L, m);
        build(v * 2 + 1, m + 1, R);
        mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
    }
}

void push(int v, int L, int R) {
    if (tup[v]) {
        if (L != R) {
            up[v * 2] = up[v];
            up[v * 2 + 1] = up[v];
            tup[v * 2] = 1;
            tup[v * 2 + 1] = 1;
        }
        t[v] = up[v] + mx[v];
        tup[v] = 0;
    }
}

void upd(int l, int r, int x, int v, int L, int R) {
    push(v, L, R);
    if (l > r)
        return;
    if (l == L && r == R) {
        up[v] = x;
        tup[v] = 1;
        push(v, L, R);
    }
    else {
        int m = (L + R) >> 1;
        upd(l, min(m, r), x, v * 2, L, m);
        upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
        t[v] = max(t[v * 2], t[v * 2 + 1]);
    }
}

int que(int l, int r, int v, int L, int R) {
    push(v, L, R);
    if (l > r)
        return -INF;
    if (l == L && r == R)
        return t[v];
    int m = (L + R) >> 1;
    return max(que(l, min(m, r), v * 2, L, m),
        que(max(m + 1, l), r, v * 2 + 1, m + 1, R));
}

signed main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    build(1, 0, n - 1);
    upd(0, n - 1, -INF, 1, 0, n - 1);

    set<pair<int, int>> st;
    st.insert({0, -INF});
    st.insert({n, INF});

    vector<int> v;
    for (int i = 0; i < n; i++) {
        while (!v.empty() && a[v.back()] < a[i])
            v.pop_back();
        lm[i] = v.empty() ? -1 : v.back();
        v.push_back(i);
    }

    v.clear();

    for (int i = n - 1; i >= 0; i--) {
        while (!v.empty() && a[v.back()] < a[i])
            v.pop_back();
        rm[i] = v.empty() ? -1 : v.back();
        v.push_back(i);
    }

    for (int i = 0; i < n; i++) {
        if (lm[i] != -1) 
            ev[lm[i]].push_back({lm[i], i});
        if (rm[i] != -1)
            ev[i].push_back({i, rm[i]});
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qr[l - 1].push_back({r - 1, i});
    }

    // for (int i = 0; i < n; i++) {
    //     for (auto p : ev[i]) {
    //         cout << p.first + 1 << " " << p.second + 1 << "\n";
    //     }
    // }


    for (int i = n - 1; i >= 0; i--) {
        for (auto p : ev[i]) {
            int x = p.second + p.second - p.first,
                val = a[p.first] + a[p.second];
            if (x >= n)
                continue;
            if (prev(st.lower_bound({x + 1, -1}))->second < val) {
                auto it = st.lower_bound({x, -1});
                while (it->second <= val) {
                    it++;
                    st.erase(prev(it));
                }
                upd(x, it->first - 1, val, 1, 0, n - 1);
                st.insert(make_pair(x, val));
            }
        }

        for (auto p : qr[i]) {
            ans[p.second] = que(i, p.first, 1, 0, n - 1);
        }

        // for (auto p : st) {
        //     cout << p.first + 1 << " " << p.second << "\n";
        // }
        // cout << que(3, 3, 1, 0, n - 1) << "\n";
        // cout << "\n";
    }

    for (int i = 0; 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