Submission #552222

#	Time	Username	Problem	Language	Result	Execution time	Memory
552222		RaresFelix	Triple Jump (JOI19_jumps)	C++17	100 / 100	1084 ms	58784 KiB

jumps

#include <bits/stdc++.h>
#define MN 500071
using namespace std;
int n, q, A[MN];
vector<pair<int, int> > OG;
struct nod {
    int delta, origm, lazy_d;
    int val, ma;
};

nod V[4 * MN];

void init(int u = 1, int s = 1, int d = n) {
    if(s != d) {
        init(u << 1, s, (s + d) >> 1);
        init(u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u].origm = V[u].ma = V[u].val = max(V[u << 1].origm, V[u << 1 | 1].origm);
    } else {
        V[u].origm = V[u].val = V[u].ma = A[s];
    }
}

void prop(int u, int s, int d) {
    if(V[u].delta < V[u].lazy_d) {
        V[u].delta = V[u].lazy_d;
        V[u].val = V[u].delta + V[u].origm;
        V[u].ma = max({V[u].ma, V[u].val});
    }
    if(s != d) {
        V[u << 1].lazy_d = max(V[u << 1].lazy_d, V[u].lazy_d);
        V[u << 1 | 1].lazy_d = max(V[u << 1 | 1].lazy_d, V[u].lazy_d);
    }
    V[u].lazy_d = 0;
}

void update(int val, int l, int r, int u = 1, int s = 1, int d = n) {
    prop(u, s, d);
    if(d < l || r < s) return;
    if(l <= s && d <= r) {
        V[u].lazy_d = val;
        prop(u, s, d);
        return;
    }
    update(val, l, r, u << 1, s, (s + d) >> 1);
    update(val, l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
    V[u].ma = max({V[u].val, V[u].ma, V[u << 1].ma, V[u << 1 | 1].ma});
}

int query(int l, int r, int u = 1, int s = 1, int d = n) {
    if(d < l || r < s) return 0;
    prop(u, s, d);
    if(l <= s && d <= r) return V[u].ma;
    return max(query(l, r, u << 1, s, (s + d) >> 1), query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d));
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> A[i];
    stack<int> S;
    init();
    for(int i = 1; i <= n; ++i) {
        while(!S.empty() && A[i] > A[S.top()]) {
            OG.push_back({S.top(), i});
            S.pop();
        }
        if(!S.empty()) OG.push_back({S.top(), i});
        S.push(i);
    }
    cin >> q;
    vector<tuple<int, int, int> > Q;
    for(int i = 1, st, dr; i <= q; ++i)
        cin >> st >> dr, Q.push_back({st, dr, i});
    vector<int> R(q + 1);
    sort(Q.rbegin(), Q.rend());
    sort(OG.rbegin(), OG.rend());
    auto it = OG.begin();
    for(auto [l, r, id] : Q) {
        while(it != OG.end() && it->first >= l) {
            update(A[it->first] + A[it->second], it->second * 2 - it->first, n);
            //printf("Update de valoare %d de la %d la n\n", A[it->first] + A[it->second], it->second * 2 - it->first);
            ++it;
        }
        R[id] = query(l, r);
    }
    for(int i = 1; i <= q; ++i) cout << R[i] << "\n";
    return 0;
}

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