Submission #1096425

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096425		duonggsimp	Triple Jump (JOI19_jumps)	C++14	0 / 100	66 ms	11964 KiB

jumps

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define xn '\n'
#define pb push_back
#define oo LONG_MAX
using namespace std;

typedef pair<ll,ll> i2;
typedef pair<ll,i2> i3;
typedef pair<i2,ll> i4;

const int N = 1e6+5;
const int M = 1e3+5;
const ll mo = 1e9+7;

ll n,m;
ll a[N];
i2 t[4*N];

void build(ll id,ll l,ll r){
    if (l == r){
        t[id].fi = a[l];
        t[id].se = l;
        return;
    }

    ll m = l + r >> 1;
    build(id*2,l,m);
    build(id*2+1,m+1,r);

    t[id] = max(t[id*2],t[id*2+1]);
}

i2 get(ll id,ll l,ll r,ll u,ll v){
    if (u > r || v < l) return {-1e9,0};
    if (u <= l && r <= v) return t[id];

    ll m = l + r >> 1;
    return max(get(id*2,l,m,u,v),get(id*2+1,m+1,r,u,v));
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (long i=1; i<=n; i++) cin >> a[i];

    cin >> m;
    build(1,1,n);
    while (m--){
        ll res = 0;
        ll u,v; cin >> u >> v;
        for (long i=u; i<=v; i++){
            i2 max1 = get(1,1,n,u,i-1);
            i2 max2 = get(1,1,n,i+(i-max1.se+1)-1,v);
            res = max(res,a[i] + max1.fi + max2.fi);
        }
        cout << res << xn;
    }

    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void build(long long int, long long int, long long int)':
jumps.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     ll m = l + r >> 1;
      |            ~~^~~
jumps.cpp: In function 'i2 get(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:40:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     ll m = l + r >> 1;
      |            ~~^~~

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