Submission #242524

#	Time	Username	Problem	Language	Result	Execution time	Memory
242524		dantoh000	Triple Jump (JOI19_jumps)	C++14	100 / 100	1293 ms	125048 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
int n,q;
int a[500005];
int ans[500005];
vector<ii> good[500005];
vector<ii> query[500005];
struct node{
    int s,e,m,ab,c,abc;
    node *l, *r;
    node (int _s, int _e) : s(_s), e(_e){
        m = (s+e)/2;
        ab = c = abc = 0;
        if (s != e){
            l = new node(s,m);
            r = new node(m+1,e);
            ab = max(l->ab,r->ab);
            c = max(l->c,r->c);
            abc = max(l->ab+r->c,max(l->abc,r->abc));
        }
        else{
            c = a[s];
        }
    }
    void up(int x, int nv){
        if (s == e){
            ab = max(ab,nv);
            abc = ab+c;
            return;
        }
        if (x > m) r->up(x,nv);
        else l->up(x,nv);
        ab = max(l->ab,r->ab);
        c = max(l->c,r->c);
        abc = max(l->ab+r->c,max(l->abc,r->abc));
    }
    iii query(int qs, int qe){
        //printf("segment tree <%d,%d>\n",qs,qe);
        if (qs == s && qe == e){
            return iii(ab,c,abc);
        }
        else if (qs > m) return r->query(qs,qe);
        else if (qe <= m) return l->query(qs,qe);
        else{
            iii L = l->query(qs,m);
            iii R = r->query(m+1,qe);
            int AB = max(get<0>(L),get<0>(R));
            int C = max(get<1>(L),get<1>(R));
            int ABC = max(get<0>(L)+get<1>(R),max(get<2>(L),get<2>(R)));
            return {AB,C,ABC};
        }
    }
} *root;
stack<ii> s;
int main(){
    scanf("%d",&n);
    for (int i = 1; i <= n; i++){
        scanf("%d",&a[i]);
    }
    for (int i = 1; i <= n; i++){
        while (s.size() && s.top().second <= a[i]){
            int A = s.top().first;
            int C = i-A+i;
            int V = a[A] + a[i];
            //printf("stack %d %d\n",A,i);
            if (C <= n) good[A].push_back({C,V});
            s.pop();
        }
        if (s.size()){
            int A = s.top().first;
            int C = i-A+i;
            int V = a[A] + a[i];
            //printf("stack %d %d\n",A,i);
            if (C <= n) good[A].push_back({C,V});
        }
        s.push({i,a[i]});
    }
    scanf("%d",&q);
    for (int i = 0; i < q; i++){
        int l,r;
        scanf("%d%d",&l,&r);
        query[l].push_back({r,i});
    }
    root = new node(1,n);
    for (int i = n; i >= 1; i--){
        for (auto x : good[i]){
            //printf("%d: updating %d with %d\n",i,x.first,x.second);
            root->up(x.first,x.second);
        }
        for (auto x : query[i]){
            //printf("%d: query %d <%d,%d>\n",i,x.second,i,x.first);
            ans[x.second] = get<2>(root->query(i,x.first));
        }
    }
    for (int i = 0; i < q; i++){
        printf("%d\n",ans[i]);
    }

}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
jumps.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~
jumps.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&q);
     ~~~~~^~~~~~~~~
jumps.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&l,&r);
         ~~~~~^~~~~~~~~~~~~~

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