Submission #955010

#	Time	Username	Problem	Language	Result	Execution time	Memory
955010		StefanSebez	Triple Jump (JOI19_jumps)	C++14	100 / 100	1045 ms	79036 KiB

jumps

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
const int N=5*1e5+50,inf=1e9;
int a[N];
int root,nc,lc[2*N],rc[2*N],maks[2*N],maks1[2*N],maksu[2*N],lazy[2*N];
void Build(int &c,int ss,int se){
    c=++nc;
    maks[c]=lazy[c]=-inf;
    if(ss==se){
        maks1[c]=a[ss];
        maksu[c]=maks1[c];
        return;
    }
    int mid=(ss+se)/2;
    Build(lc[c],ss,mid);
    Build(rc[c],mid+1,se);
    maks1[c]=max(maks1[lc[c]],maks1[rc[c]]);
    maksu[c]=maks1[c];
}
void update(int c,int qval){
    lazy[c]=max(lazy[c],qval);
    maks[c]=max(maks[c],qval);
    maksu[c]=max(maksu[c],maks1[c]+qval);
}
void push(int c){
    update(lc[c],lazy[c]);
    update(rc[c],lazy[c]);
    lazy[c]=-inf;
}
void Update(int c,int ss,int se,int qs,int qe,int qval){
    //if(!c) c=++nc;
    if(qs>qe) return;
    if(qs<=ss && se<=qe){
        update(c,qval);
        //printf("%i %i %i: %i %i %i\n",c,ss,se,maks[c],maks1[c],maksu[c]);
        return;
    }
    if(qe<ss || se<qs) return;
    int mid=(ss+se)/2;
    push(c);
    Update(lc[c],ss,mid,qs,qe,qval);
    Update(rc[c],mid+1,se,qs,qe,qval);
    maks[c]=max(maks[lc[c]],maks[rc[c]]);
    maksu[c]=max(maksu[lc[c]],maksu[rc[c]]);
    //printf("%i %i %i: %i %i %i\n",c,ss,se,maks[c],maks1[c],maksu[c]);
}
int Get(int c,int ss,int se,int qs,int qe){
    //printf("%i %i: %i %i %i %i\n",ss,se,maks[c],maks1[c],maksu[c],lazy[c]);
    if(qs<=ss && se<=qe) {
        return maksu[c];
    }
    if(qe<ss || se<qs) return -inf;
    int mid=(ss+se)/2;
    push(c);
    return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
}
int main()
{
    int n;scanf("%i",&n);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    int Q;scanf("%i",&Q);pair<pair<int,int>,int>Qs[Q+10];
    for(int i=1;i<=Q;i++) {scanf("%i%i",&Qs[i].fi.fi,&Qs[i].fi.se);Qs[i].se=i;}
    vector<int>mono;
    vector<int>R[n+10];
    for(int i=1;i<=n;i++){
        while(mono.size() && a[mono.back()]<a[i]){
            R[mono.back()].pb(i);
            mono.pop_back();
        }
        //if(mono.size() && a[mono.back()]==a[i]){R[mono.back()].pb(i);mono.pop_back();}
        mono.pb(i);
    }
    mono.clear();
    for(int i=1;i<=n;i++){
        while(mono.size() && a[mono.back()]<a[i]){
			mono.pop_back();
            //R[mono.back()].pb(i);
            //int temp=mono.back();
            //while(mono.size() && a[mono.back()]==a[temp]) mono.pop_back();
        }
        if(mono.size()) R[mono.back()].pb(i);
        mono.pb(i);
        //for(auto j:mono) printf("%i ",j);
        //printf("\n");
    }
    //printf("*\n");
    //for(int i=1;i<=n;i++) for(auto j:R[i]) printf("%i %i\n",i,j);
    /*vector<int>R[n+10];
    for(int i=1;i<=n;i++){
        //printf("%i: ",i);
        //int mx=a[i];
        for(int j=i+1;j<=n;j++){
            //mx=max(mx,a[j]);
            int mx=0;
            for(int k=i+1;k<j;k++){
                mx=max(mx,a[k]);
            }
            if(mx<a[i] && mx<a[j]) R[i].pb(j);//printf("%i ",R[i].back());}
        }
        //printf("\n");
    }*/
    Build(root,1,n);
    int res[Q+10]={0};
    sort(Qs+1,Qs+Q+1);
    for(int i=n,j=Q;i>=1;i--){
        for(auto j:R[i]){//if(R[i]!=0){
            //a=i,b=R[i], b-a<=c-b, 2b-a=2R[i]-i<=c
            if(2*j-i<=n) Update(root,1,n,2*j-i,n,a[i]+a[j]);//printf("%i %i %i %i: %i\n",i,j,2*j-i,n,a[i]+a[j]);}
        }
        while(j>=1 && Qs[j].fi.fi==i){
            res[Qs[j].se]=Get(root,1,n,Qs[j].fi.fi,Qs[j].fi.se);
            //printf("%i %i %i %i\n",res[Qs[j].se],Qs[j].fi.fi,Qs[j].fi.se,Qs[j].se);
            j--;
        }
        //if(i==3) printf("- %i -\n",Get(root,1,n,3,5));
    }
    for(int i=1;i<=Q;i++) printf("%i ",res[i]);
    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:63:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     int n;scanf("%i",&n);
      |           ~~~~~^~~~~~~~~
jumps.cpp:64:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~
jumps.cpp:65:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     int Q;scanf("%i",&Q);pair<pair<int,int>,int>Qs[Q+10];
      |           ~~~~~^~~~~~~~~
jumps.cpp:66:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     for(int i=1;i<=Q;i++) {scanf("%i%i",&Qs[i].fi.fi,&Qs[i].fi.se);Qs[i].se=i;}
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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