Submission #206720

#	Time	Username	Problem	Language	Result	Execution time	Memory
206720		laoriu	Triple Jump (JOI19_jumps)	C++14	100 / 100	1136 ms	83412 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pp;
int n,A[500002],q;
vector <pp> P;
struct query
{
    int l,r,pos;
    bool operator < (const query&a)
    const
    {
        return (l>a.l);
    }
};
query Q[500002];

long long res[500002];
struct node
{
    long long a,val,vmax;
};
node it[2000002];
void build(int id,int l,int r)
{
    if (l==r)
    {
        it[id].a=A[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    it[id].a=max(it[id*2].a,it[id*2+1].a);
}
void down(int id)
{
    long long t=it[id].vmax;
    it[id*2].vmax=max(it[id*2].vmax,t);it[id*2].val=max(it[id*2].val,it[id*2].a+t);
    it[id*2+1].vmax=max(it[id*2+1].vmax,t);it[id*2+1].val=max(it[id*2+1].val,it[id*2+1].a+t);
}
void update(int id,int l,int r,int a,int b,long long val)
{
    if (l>b||r<a) return;
    if (l>=a&&r<=b)
    {
        it[id].vmax=max(it[id].vmax,val);
        it[id].val=max(it[id].val,it[id].a+val);
        return;
    }
    down(id);
    int mid=(l+r)/2;
    update(id*2,l,mid,a,b,val);
    update(id*2+1,mid+1,r,a,b,val);
    it[id].val=max(it[id*2].val,it[id*2+1].val);
}
long long query(int id,int l,int r,int a,int b)
{
    if (l>b||r<a) return 0;
    if (l>=a&&r<=b) return it[id].val;
    down(id);
    int mid=(l+r)/2;
    return max(query(id*2,l,mid,a,b),query(id*2+1,mid+1,r,a,b));
}
void prepare()
{
    deque <int> dq;
    for (int i=1;i<=n;i++)
    {
        while (!dq.empty()&&A[dq.back()]<A[i]) dq.pop_back();
        if (!dq.empty()) P.push_back({dq.back(),i});
        dq.push_back(i);
    }
    while (!dq.empty()) dq.pop_back();
    for (int i=n;i>=1;i--)
    {
        while (!dq.empty()&&A[dq.back()]<=A[i]) dq.pop_back();
        if (!dq.empty()) {P.push_back({i,dq.back()});}
        dq.push_back(i);
    }
    sort(P.begin(),P.end(),greater<pp>());
   // for (int i=0;i<P.size();i++)
       // cout<<P[i].first<<' '<<P[i].second<<'\n';
}
void solve()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>A[i];
    prepare();
    cin>>q;
    for (int i=1;i<=q;i++)
    {
        cin>>Q[i].l>>Q[i].r;
        Q[i].pos=i;
    }
    for (int i=1;i<=4*n;i++) it[i].a=it[i].val=it[i].vmax=0;
    build(1,1,n);
    sort(Q+1,Q+q+1);
    int d=0;
    for (int i=1;i<=q;i++)
    {
        while (d<P.size()&&P[d].first>=Q[i].l)
        {
            int c=2*P[d].second-P[d].first;
            if (c<=n) update(1,1,n,c,n,(long long) A[P[d].first]+A[P[d].second]);
            d++;
        }
        res[Q[i].pos]=query(1,1,n,Q[i].l,Q[i].r);
    }
    for (int i=1;i<=q;i++)
        cout<<res[i]<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //  freopen("jump1000.inp","r",stdin);
  //  freopen("jump1000.out","w",stdout);
    solve();
}

Compilation message (stderr)

jumps.cpp: In function 'void solve()':
jumps.cpp:102:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while (d<P.size()&&P[d].first>=Q[i].l)
                ~^~~~~~~~~

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