Submission #200115

#	Time	Username	Problem	Language	Result	Execution time	Memory
200115		gs18115	Triple Jump (JOI19_jumps)	C++14	100 / 100	1221 ms	138120 KiB

jumps

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct node
{
    ll am,bm,sm;
    node(ll x=-INF,ll y=-INF):am(x),bm(y),sm(x+y){}
    node(ll x,ll y,ll z):am(x),bm(y),sm(z){}
    node operator^(node x)
    {
        return node(max(am,x.am),max(bm,x.bm),max({sm,x.sm,bm+x.am}));
    }
};
ll a[500010],b[500010];
struct seg
{
    node t[2000010];
    seg()
    {
        fill(t,t+2000010,node());
    }
    void si(int n,int s,int e,int x)
    {
        if(s==e)
        {
            t[n]=node(a[s],b[s]);
            return;
        }
        int m=s+e>>1;
        if(x>m)
            si(n*2+1,m+1,e,x);
        else
            si(n*2,s,m,x);
        t[n]=t[n*2]^t[n*2+1];
        return;
    }
    node sq(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return node();
        if(S<=s&&e<=E)
            return t[n];
        int m=s+e>>1;
        return sq(n*2,s,m,S,E)^sq(n*2+1,m+1,e,S,E);
    }
}st;
vector<pl>qv[500010];
vector<pi>av[500010];
ll ans[500010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n;
    for(int i=0;i++<n;)
        cin>>a[i],b[i]=-INF;
    vector<int>v;
    v.eb(n);
    for(int i=n;--i>0;)
    {
        while(!v.empty())
        {
            int j=v.back();
            if(2*j-i<=n)
                qv[i].eb(2*j-i,a[i]+a[j]);
            if(a[j]<=a[i])
                v.pop_back();
            else
                break;
        }
        v.eb(i);
    }
    cin>>q;
    for(int i=0;i<q;i++)
    {
        int l,r;
        cin>>l>>r;
        av[l].eb(r,i);
    }
    for(int i=n;i>0;i--)
    {
        for(pl&t:qv[i])
            if(b[t.fi]<t.se)
                b[t.fi]=t.se,st.si(1,1,n,t.fi);
        for(pi&t:av[i])
            ans[t.se]=st.sq(1,1,n,i+2,t.fi).sm;
    }
    for(int i=0;i<q;i++)
        cout<<ans[i]<<'\n';
    cout.flush();
    return 0;
}

Compilation message (stderr)

jumps.cpp: In member function 'void seg::si(int, int, int, int)':
jumps.cpp:42:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m=s+e>>1;
               ~^~
jumps.cpp: In member function 'node seg::sq(int, int, int, int, int)':
jumps.cpp:56:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m=s+e>>1;
               ~^~

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