Submission #242392

#	Time	Username	Problem	Language	Result	Execution time	Memory
242392		tqbfjotld	Triple Jump (JOI19_jumps)	C++14	100 / 100	1168 ms	99416 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

int n;
long long arr[500005];
vector<pair<int,int> > abpairs;
long long ans[500005];
vector<pair<pair<int,int>,int> > queries;

struct node{
    int s,e;
    long long ab,c,abc;
    node *l,*r;
    node(int _s, int _e){
        s = _s;
        e = _e;
        if (s==e){
            c = arr[s];
            ab = -999999999999LL;
            abc = -999999999999LL;
        }
        else{
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
            mergeval();
        }
    }
    void mergeval(){
        if (s==e){
            abc = ab+c;
        }
        else{
            ab = max(l->ab,r->ab);
            c = max(l->c,r->c);
            abc = max(max(l->abc,r->abc),l->ab+r->c);
        }
    }
    void upd(int pos, long long val){
        if (s==e){
            ab = max(ab,val);
        }
        else if (pos>(s+e)/2){
            r->upd(pos,val);
        }
        else{
            l->upd(pos,val);
        }
        mergeval();
    }
    pair<long long,pair<long long,long long> > query(int a, int b){
        if (a<=s && e<=b){
            return {abc,{ab,c}};
        }
        if (b<=(s+e)/2){
            return l->query(a,b);
        }
        if (a>(s+e)/2){
            return r->query(a,b);
        }
        auto lv = l->query(a,b);
        auto rv = r->query(a,b);
        return {max(max(lv.first,rv.first),lv.second.first+rv.second.second),{max(lv.second.first,rv.second.first),max(lv.second.second,rv.second.second)}};
    }
}*root;


int main(){
    scanf("%d",&n);
    for (int x = 0; x<n; x++){
        scanf("%lld",&arr[x]);
    }
    root = new node(0,n+3);
    stack<long long> st;
    for (int x = 0; x<n; x++){
        if (st.empty()){
            st.push(x);
            continue;
        }
        while ((!st.empty()) && arr[x]>=arr[st.top()]){
            abpairs.push_back({st.top(),x});
            st.pop();
        }
        if (!st.empty()){
            abpairs.push_back({st.top(),x});
        }
        st.push(x);
    }

    sort(abpairs.begin(),abpairs.end());

    int q;
    scanf("%d",&q);
    for (int x = 0; x<q; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        a--;b--;
        queries.push_back({{a,b},x});
    }
    sort(queries.begin(),queries.end());
    int c = abpairs.size()-1;
    for (int x = q-1; x>=0; x--){
        while (c>=0 && abpairs[c].first>=queries[x].first.first){
            int pos = abpairs[c].second*2-abpairs[c].first;
            root->upd(min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]);
            //printf("upd %d, %d\n",min(pos,n+1),arr[abpairs[c].first]+arr[abpairs[c].second]);
            c--;
        }
        ans[queries[x].second] = root->query(queries[x].first.first,queries[x].first.second).first;
    }
    for (int x = 0; x<q; x++){
        printf("%lld\n",ans[x]);
    }

}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&arr[x]);
         ~~~~~^~~~~~~~~~~~~~~~
jumps.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:95:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~

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