Submission #219549

#	Time	Username	Problem	Language	Result	Execution time	Memory
219549		MKopchev	Triple Jump (JOI19_jumps)	C++14	100 / 100	1743 ms	46676 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
const int nmax=(1<<19)+42,MX=20;
int n,q;

int inp[nmax];

vector< pair<int,int> > start;

struct info
{
    int best_sum;
    int mx_first;
    int mx_second;
};
info tree[2*nmax];

info my_merge(info l,info r)
{
    info ret;

    ret.mx_first=max(l.mx_first,r.mx_first);
    ret.mx_second=max(l.mx_second,r.mx_second);

    ret.best_sum=max(l.best_sum,r.best_sum);
    ret.best_sum=max(ret.best_sum,l.mx_first+r.mx_second);
    return ret;
}
void update(int node,int l,int r,int pos,pair<int,int> val)
{
    if(l==r)
    {
        tree[node].mx_first=max(tree[node].mx_first,val.first);
        tree[node].mx_second=val.second;
        tree[node].best_sum=tree[node].mx_first+tree[node].mx_second;
        return;
    }

    int av=(l+r)/2;
    if(pos<=av)update(node*2,l,av,pos,val);
    else update(node*2+1,av+1,r,pos,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

info query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return tree[node];
    int av=(l+r)/2;

    info ret;ret.best_sum=0;ret.mx_first=0;ret.mx_second=0;

    if(lq<=av)ret=my_merge(ret,query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ret=my_merge(ret,query(node*2+1,av+1,r,max(av+1,lq),rq));
    return ret;
}

stack<int> active;

struct que
{
    int l,r,id;
};
que help[nmax];
bool cmp(que a,que b)
{
    return a.l>b.l;
}

int output[nmax];
int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

    for(int i=1;i<=n;i++)
    update(1,1,n,i,{0,inp[i]});

    for(int i=1;i<=n;i++)
    {

        while(active.size()&&inp[active.top()]<=inp[i])
        {
            start.push_back({active.top(),i});
            active.pop();
        }

        if(active.size())start.push_back({active.top(),i});

        active.push(i);
    }
    sort(start.begin(),start.end());

    reverse(start.begin(),start.end());
    /*
    cout<<"start: "<<endl;
    for(auto k:start)cout<<k.first<<" "<<k.second<<endl;
    */
    scanf("%i",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%i%i",&help[i].l,&help[i].r);
        help[i].id=i;
    }
    sort(help+1,help+q+1,cmp);

    int pointer_start=0;

    int pointer_help=1;

    for(int l=n;l>=1;l--)
    {
        //cout<<"l= "<<l<<" "<<start[pointer_start].first<<" "<<pointer_start<<" "<<pointer_help<<endl;

        while(pointer_start<start.size()&&start[pointer_start].first==l)
        {
            int a=start[pointer_start].first;
            int b=start[pointer_start].second;
            int c=b+b-a;

            //cout<<"a= "<<a<<" b= "<<b<<" c= "<<c<<endl;

            if(c<=n)
            {
                update(1,1,n,c,{inp[a]+inp[b],inp[c]});

                //cout<<"update "<<c<<" "<<inp[a]+inp[b]<<" with "<<inp[c]<<endl;
            }

            pointer_start++;
        }

        while(pointer_help<=q&&help[pointer_help].l==l)
        {
            output[help[pointer_help].id]=query(1,1,n,help[pointer_help].l,help[pointer_help].r).best_sum;
            pointer_help++;
        }
    }
    for(int i=1;i<=q;i++)
        printf("%i\n",output[i]);
    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:115:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(pointer_start<start.size()&&start[pointer_start].first==l)
               ~~~~~~~~~~~~~^~~~~~~~~~~~~
jumps.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:74:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~
jumps.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&help[i].l,&help[i].r);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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