Submission #1313652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313652		yessimkhan	Triple Jump (JOI19_jumps)	C++20	5 / 100	4091 ms	18356 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;

struct tree{
    int cnt , l , r;
};

int n , q , a[N] , mx[4 * N];
tree t[4 * N];

tree merge(tree a , tree b){

    tree res = a;

    if (a.cnt != b.cnt){
        if (a.cnt < b.cnt) res = b;
        else res = a;
    }

    else {
        res.cnt = a.cnt;
        res.l = min(a.l , b.l);
        res.r = max(a.r , b.r);
    }

    return res; 
}

void build(int v , int tl , int tr){
    if (tl == tr){
        t[v] = {a[tl] , 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] = merge(t[v * 2] , t[v * 2 + 1]);

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

tree get(int v , int tl , int tr , int l , int r){
    if (tr < l or r < tl) return {0 , 0 , 0};
    if (l <= tl and tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    return merge(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].cnt = 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] = merge(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;
        bool t = 0;
        vector<int> p;

        cin >> l >> r;

        while(p.size() != r - l + 1 and p.size() < 100){
            
            t = 1 - t;

            auto gt = get(1 , 1 , n , l , r);

            int pos = 0;

            if (t == 0) pos = gt.l;
            else pos = gt.r;

            p.pb(pos);

            update(1 , 1 , n , pos , 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: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 27
• Subtask 4: 0 / 54