oj.uz

Submission #1096425

# Submission time Handle Problem Language Result Execution time Memory
1096425 2024-10-04T12:29:04 Z duonggsimp Triple Jump (JOI19_jumps) C++14
0 / 100
 66 ms 11964 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 11960 KB Output is correct
2 Correct 56 ms 11964 KB Output is correct
3 Correct 51 ms 11864 KB Output is correct
4 Correct 65 ms 11868 KB Output is correct
5 Incorrect 66 ms 11764 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -