Submission #147809

#	Time	Username	Problem	Language	Result	Execution time	Memory
147809		Alexa2001	Triple Jump (JOI19_jumps)	C++17	100 / 100	1219 ms	93396 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5e5 + 5;
const int inf = 1e9;

vector<int> start[Nmax], query[Nmax];
vector<pair<int,int>> v;

int a[Nmax], st[Nmax];
int n, L[Nmax], R[Nmax];
int ans[Nmax];


#define left_son ((node<<1))
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

class SegTree
{
    int best[Nmax<<2];
    int mx[Nmax<<2];
    int lazy[Nmax<<2];

    void propag(int node)
    {
        if(!lazy[node]) return;

        best[left_son] = max(best[left_son], mx[left_son] + lazy[node]);
        best[right_son] = max(best[right_son], mx[right_son] + lazy[node]);
        lazy[left_son] = max(lazy[left_son], lazy[node]);
        lazy[right_son] = max(lazy[right_son], lazy[node]);
        lazy[node] = 0;
    }

public:
    void init(int node, int st, int dr)
    {
        lazy[node] = 0;
        best[node] = -inf;

        if(st == dr)
        {
            mx[node] = a[st];
            return;
        }    

        init(left_son, st, mid);
        init(right_son, mid+1, dr);

        mx[node] = max(mx[left_son], mx[right_son]);
    }

    void update(int node, int st, int dr, int L, int R, int coef)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] = max(lazy[node], coef);
            best[node] = max(best[node], mx[node] + coef);
            return;
        }

        propag(node);

        if(L <= mid) update(left_son, st, mid, L, R, coef);
        if(mid < R) update(right_son, mid+1, dr, L, R, coef);

        best[node] = max(best[left_son], best[right_son]);
    }
    
    int query(int node, int st, int dr, int L, int R)
    {
        if(L <= st && dr <= R)
            return best[node];

        propag(node);
        
        int ans = -inf;
        if(L <= mid) ans = max(ans, query(left_son, st, mid, L, R));
        if(mid < R) ans = max(ans, query(right_son, mid+1, dr, L, R));
        return ans;
    }

} aint;

void fnd()
{
    int i, nr = 0;

    st[0] = 0;
    a[0] = inf;

    for(i=1; i<=n; ++i)
    {
        while(a[st[nr]] <= a[i])
        {
            v.push_back({st[nr], i});
            --nr;
        }

        v.push_back({st[nr], i});
        st[++nr] = i;
    }
}

int main()
{
   // freopen("triple.in", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);
    
    cin >> n;

    int i, q;
    for(i=1; i<=n; ++i) cin >> a[i];
    
    fnd();

    cin >> q;
    for(i=1; i<=q; ++i) cin >> L[i] >> R[i];

    for(auto it : v)
        start[it.first].push_back(it.second);

    for(i=1; i<=q; ++i)
        query[L[i]].push_back(i);
    
    aint.init(1, 1, n);

    for(i=n; i; --i)
    {
        for(auto it : start[i])
        {
            int R = 2 * it - i;
            if(R <= n)
                aint.update(1, 1, n, R, n, a[i] + a[it]);
        }

        for(auto it : query[i])
            ans[it] = aint.query(1, 1, n, i, R[it]);
    }

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