Submission #134502

#	Time	Username	Problem	Language	Result	Execution time	Memory
134502		RezwanArefin01	Triple Jump (JOI19_jumps)	C++17	100 / 100	1417 ms	111600 KiB

jumps

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

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 5e5 + 10;
const ll inf = 1e18;

int n, q, a[N], ans[N];
vector<ii> Q[N]; 
vector<int> B[N]; 

struct Node {
    ll a, f, af; 
    Node(ll a = -inf, ll f = -inf, ll af = -inf): 
        a(a), f(f), af(af) {}
} t[N << 2]; 

Node merge(Node l, Node r) {
    return Node(max(l.a, r.a), max(l.f, r.f), max({l.af, r.af, l.f + r.a}));
}

void update(int node, int l, int r, int i, int x, int f) {
    if(l == r) {
        if(f) t[node].f = max(t[node].f, (ll)x); 
        else t[node].a = max(t[node].a, (ll)x); 
        t[node].af = max(-inf, t[node].f + t[node].a);
    } else {
        int m = l + r >> 1; 
        if(i <= m) update(node << 1, l, m, i, x, f); 
        else update(node << 1 | 1, m + 1, r, i, x, f);
        t[node] = merge(t[node << 1], t[node << 1 | 1]); 
    }
}

Node query(int node, int l, int r, int i, int j) {
    if(r < i || l > j) return Node(); 
    if(i <= l && r <= j) return t[node];
    int m = l + r >> 1; 
    return merge(query(node << 1, l, m, i, j), 
           query(node << 1 | 1, m + 1, r, i, j));
}

int main(int argc, char const *argv[]) {
#ifdef LOCAL
    freopen("in", "r", stdin);
#endif
    scanf("%d", &n);

    stack<int> st;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]); 

        while(st.size() && a[st.top()] <= a[i]) {
            B[st.top()].push_back(i); 
            st.pop();
        }
        if(st.size()) {
            B[st.top()].push_back(i); 
        }
        st.push(i);

        update(1, 1, n, i, a[i], 0);
    }   

    scanf("%d", &q);
    for(int i = 1; i <= q; ++i) {
        int l, r;
        scanf("%d %d", &l, &r); 
        Q[l].emplace_back(r, i);
    }

    for(int i = n; i >= 1; --i) {
        for(int b : B[i]) if(2 * b - i <= n) {
            update(1, 1, n, 2 * b - i, a[i] + a[b], 1);
        }
        for(ii x : Q[i]) {
            ans[x.second] = query(1, 1, n, i, x.first).af; 
        }
    }

    for(int i = 1; i <= q; ++i) {
        printf("%lld\n", ans[i]);
    }
}

Compilation message (stderr)

jumps.cpp: In function 'void update(int, int, int, int, int, int)':
jumps.cpp:30:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = l + r >> 1; 
                 ~~^~~
jumps.cpp: In function 'Node query(int, int, int, int, int)':
jumps.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
jumps.cpp: In function 'int main(int, const char**)':
jumps.cpp:84:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
         printf("%lld\n", ans[i]);
                          ~~~~~~^
jumps.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
jumps.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]); 
         ~~~~~^~~~~~~~~~~~~
jumps.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
jumps.cpp:70: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