Submission #1313646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313646		yessimkhan	Triple Jump (JOI19_jumps)	C++20	0 / 100	20 ms	14244 KiB

jumps

#include <bits/stdc++.h>

#define int long long
#define ent '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define PRaim_bek_abi ios_base::sync_with_stdio(0);cin.tie(0);

using namespace std;

const int N = 5e5+5 , maxn = 3e5 + 5;
const int MOD = 1e9+7;

int n , q , a[N] , mx[4 * N];
pair<int , int> t[4 * N];

void build(int v , int tl , int tr){
    if (tl == tr){
        t[v] = {a[tl] , tl};
        mx[v] = a[tl];
        return;
    }

    int tm = (tl + tr) / 2;

    build(v * 2 , tl , tm) , build(v * 2 + 1 , tm + 1,  tr);

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

    mx[v] = max(mx[v * 2] , mx[v * 2 + 1]);
}

pair<int , int> get(int v , int tl , int tr , int l , int r){
    if (tr < l or r < tl) return {0 , 0};
    if (l <= tl and tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return max(get(v * 2 , tl , tm , l , r) , get(v * 2 + 1 , tm + 1, tr , l , r));
}

int gmx(int v , int tl , int tr , int l , int r){
    if (tr < l or r < tl) return 0;
    if (l <= tl and tr <= r) return mx[v];
    int tm = (tl + tr) / 2;
    return max(gmx(v * 2 , tl , tm , l , r) , gmx(v * 2 + 1 , tm + 1, tr , l , r));
}

void update(int v , int tl , int tr , int i , int x){
    if (tl == tr){
        t[v].first = x;
        return;
    }
    int tm = (tl + tr) / 2;
    if (i <= tm) update(v * 2 , tl , tm , i , x);
    else update(v * 2 + 1 , tm + 1 , tr , i , x);

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

void arkanefury228(){

    cin >> n;

    for (int i = 1; i <= n; i++){

        cin >> a[i];

    }

    cin >> q;

    build(1 , 1 , n);

    while(q--){

        int l , r , ans = 0;
        vector<int> p;

        cin >> l >> r;

        while(p.size() != r - l + 1 and p.size() < 20){
            
            pair<int , int> gt = get(1 , 1 , n , l , r);

            p.pb(gt.second);

            update(1 , 1 , n , gt.second , 0);
        }

        sort(all(p));

        for (int i = 0; i < p.size(); i++){
            for (int j = i + 1; j < p.size(); j++){
                if (p[j] - p[i] + 1 <= 2) continue;
                ans = max(ans , a[p[j]] + a[p[i]] + gmx(1 , 1 , n , p[i] + 1 , (p[i] + p[j]) / 2));
            }
        }

        for (auto i : p){
            update(1 , 1 , n , i , a[i]);
        }

        cout << ans << ent;
    }
}


signed main(){

    PRaim_bek_abi

    int t=1;
    //cin>>t;
    for (int respagold = 1; respagold <= t; respagold++) arkanefury228();
}

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