Submission #716514

#	Time	Username	Problem	Language	Result	Execution time	Memory
716514		ooo	Triple Jump (JOI19_jumps)	C++14	100 / 100	942 ms	95896 KiB

jumps

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

const int nu = 5e5+5;
int n, query, a[nu], x[nu], y[nu];
int  lon[nu], ans[nu];
vector<int> q[nu], be[nu];
stack<int> st1, st2;
int lazy[nu*4], it[nu*4], ma[nu*4];
void build(int id, int l, int r)
{
    if(l == r) ma[id] = a[l];
    else
    {
        int mid = (l+r)/2;
        build(id*2, l, mid);
        build(id*2+1, mid+1, r);
        ma[id] = max(ma[id*2], ma[id*2+1]);
    }
}
void update(int id, int l, int r, int u, int v, int val)
{
    if(v < l || u > r) return ;
    else if(u <= l && r <= v)
    {
        it[id] = max(it[id], val+ma[id]);
        lazy[id] = max(lazy[id], val);
    }
    else
    {
        int mid = (l+r)/2;
        it[id*2] = max(it[id*2], lazy[id]+ma[id*2]); lazy[id*2] = max(lazy[id*2], lazy[id]);
        it[id*2+1] = max(it[id*2+1], lazy[id]+ma[id*2+1]); lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
        lazy[id] = -1e9;

        update(id*2, l, mid, u, v, val);
        update(id*2+1, mid+1, r, u, v, val);
        it[id] = max(it[id*2], it[id*2+1]);
    }
}
int getmax(int id, int l, int r, int u, int v)
{
    if(v < l || u > r) return -1e9;
    else if(u <= l && r <= v) return it[id];
    else
    {
        int mid = (l+r)/2;
        it[id*2] = max(it[id*2], lazy[id]+ma[id*2]); lazy[id*2] = max(lazy[id*2], lazy[id]);
        it[id*2+1] = max(it[id*2+1], lazy[id]+ma[id*2+1]); lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
        lazy[id] = -1e9;

        return max(getmax(id*2, l, mid, u, v), getmax(id*2+1, mid+1, r, u, v));
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    cin >> query;
    for(int i = 1; i <= query; ++i)
    {
        cin >> x[i] >> y[i];
        q[x[i]].push_back(i);
    }

    st1.push(n+1); st2.push(0);
    for(int i = n; i > 0; --i)
    {
        while(int(st1.size()) > 1 && a[st1.top()] < a[i]) st1.pop();
        //while(int(st2.size()) > 1 && a[st2.top()] > a[i]) st2.pop();
        //be[i] = st2.top();
        lon[i] = st1.top();
        //st2.push(i);
        st1.push(i);
    }

    for(int i = 1; i <= n; ++i)
    {
        while(int(st2.size()) > 1 && a[st2.top()] < a[i]) st2.pop();
        be[st2.top()].push_back(i);
        st2.push(i);
    }
    build(1, 1, n);
    for(int i = 1; i <= 4*n; ++i) it[i] = lazy[i] = -1e9;

    for(int i = n; i > 0; --i)
    {
        int aa = i; int b;
        int c = 2*b-aa;
        for(int j = 0; j < int(be[i].size()); ++j)
        {
            int qq = be[i][j];
            if(qq <= n && 2*qq-i <= n) update(1, 1, n, 2*qq-i, n, a[i]+a[qq]);
        }
       // if(be[i] <= n && c <= n) update(1, 1, n, c, n, a[i]+a[be[i]]), cout << c << ' ' << n << ' ' <<  a[i]+a[be[i]] << ' ' <<  i << '\n';
        b = lon[i]; c = 2*b-aa;
        if(lon[i] <= n && c <= n) update(1, 1, n, c, n, a[i]+a[lon[i]]);

        for(int j = 0; j < int(q[i].size()); ++j)
        {
            int p = q[i][j];
            ans[p] = getmax(1, 1, n, x[p], y[p]);
        }
    }
    for(int i = 1; i <= query; ++i) cout << ans[i] << '\n';
    return 0;
}

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