Submission #616073

#	Time	Username	Problem	Language	Result	Execution time	Memory
616073		Ahmadsm2005	Triple Jump (JOI19_jumps)	C++17	100 / 100	977 ms	98316 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;
int N,Q,A[500000],L,R,ANS[500000];
int S1[2000000],S2[2000000],S3[2000000];
vector<pair<int,int>>PA[500000];
int seg[2000000];
/*void upd2(int T,int v,int LL=0,int RR=500000,int idx=0){
    if(LL == RR && LL == T){seg[idx] = max(seg[idx],v);return;}
    else if(LL > T || RR < T)return;
    upd2(T,v,LL,(LL+RR)/2,idx*2+1),upd2(T,v,(LL+RR)/2+1,RR,idx*2+2);
}
int query2(int L,int R,int LL=0,int RR=500000,int idx=0){
    if(LL >= L && RR <= R)return seg[idx];
    else if(LL > R || RR < L) return 0;
    return max(query2(L,R,LL,(LL+RR)/2,idx*2+1),query2(L,R,(LL+RR)/2+1,RR,idx*2+2));
}*/
void upd(int T,int v,int LL = 0,int RR = 500000,int idx = 0){
    if(LL == RR && LL == T){
        S1[idx] = max(v,S1[idx]);
        S2[idx] = A[T];
        S3[idx] = S1[idx] + A[T];
        return;
    }
    else if(LL > T || RR < T)return;
    upd(T,v,LL,(LL+RR)/2,idx*2+1),upd(T,v,(LL+RR)/2+1,RR,idx*2+2);
    S3[idx] = max({S3[idx*2+1],S3[idx*2+2],S1[idx*2+1] + S2[idx*2+2]});
    S1[idx] = max(S1[idx*2+1],S1[idx*2+2]);
    S2[idx] = max(S2[idx*2+1],S2[idx*2+2]);
}
pair<pair<int,int>,int>query(int L,int R,int LL=0,int RR=500000,int idx=0){
    if(RR <= R && LL >= L){
        return {{S3[idx],S1[idx]},S2[idx]};
    }
    else if(LL > R || RR < L)return {{(int)-3e8,0},0};
    pair<pair<int,int>,int>F1 = query(L,R,LL,(LL+RR)/2,idx*2+1);
    pair<pair<int,int>,int>F2 = query(L,R,(LL+RR)/2+1,RR,idx*2+2);
    F1.first.first = max({F1.first.first,F2.first.first,F1.first.second + F2.second});
    F1.first.second = max(F1.first.second,F2.first.second);
    F1.second = max(F1.second,F2.second);
    return F1;
}
void CALC(){
    stack<pair<int,int>>F;
    for(int i = 0; i < N; i += 1){
        while(F.size()){
            pair<int,int>TOP = F.top();
            PA[TOP.second].push_back({i, i * 2 - TOP.second});
            if(TOP.first > A[i])break;
            F.pop();
        }
        F.push({A[i],i});
    }
}
int32_t main()
{
    cin.tie(0),iostream::sync_with_stdio(0);
    cin>>N;
    for(int i = 0; i < N; i += 1){
        cin>>A[i];
        upd(i,0);
    }
    CALC();
    cin>>Q;
    vector<array<int,3>>STO;
    for(int i = 0; i < Q; i += 1){
        cin>>L>>R,L--,R--;
        STO.push_back({L,R,i});
    }
    int LST = N;
    sort(STO.rbegin(),STO.rend());
    for(int i = 0; i < Q; i += 1){
        while(LST > STO[i][0]){
            LST--;
            for(int l = 0; l < PA[LST].size();l++){
                upd(PA[LST][l].second,A[PA[LST][l].first] + A[LST]);
            }
        }
        //cout<<STO[i][1]<<endl;
        ANS[STO[i][2]] = query(STO[i][0],STO[i][1]).first.first;
    }
    for(int i = 0; i < Q; i += 1)cout<<ANS[i]<<'\n';
}

Compilation message (stderr)

jumps.cpp: In function 'int32_t main()':
jumps.cpp:75:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |             for(int l = 0; l < PA[LST].size();l++){
      |                            ~~^~~~~~~~~~~~~~~~

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