Submission #863923

#	Time	Username	Problem	Language	Result	Execution time	Memory
863923		lolismek	Triple Jump (JOI19_jumps)	C++14	0 / 100	54 ms	8356 KiB

jumps

#include <algorithm>
#include <iostream>
#include <vector>

#define pii pair <int, int>

using namespace std;

const int NMAX = 5e5;

int v[NMAX + 1];

namespace AINT{
    pii aint[4 * NMAX + 1];

    void build(int node, int left, int right){
        if(left == right){
            aint[node] = {v[left], left};
            return;
        }

        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);

        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }

    void update(int node, int left, int right, int pos, int val){
        if(left == right){
            aint[node] = {val, pos};
            return;
        }

        int mid = (left + right) / 2;
        if(pos <= mid){
            update(2 * node, left, mid, pos, val);
        }else{
            update(2 * node + 1, mid + 1, right, pos, val);
        }

        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
    }

    pii query(int node, int left, int right, int l, int r){
        if(l <= left && right <= r){
            return aint[node];
        }

        int mid = (left + right) / 2;
        pii ans = {0, 0};
        if(l <= mid){
            ans = max(ans, query(2 * node, left, mid, l, r));
        }
        if(mid + 1 <= r){
            ans = max(ans, query(2 * node + 1, mid + 1, right, l, r));
        }

        return ans;
    }
}

bool ok(vector <int> v){
    if((int)v.size() < 3){
        return false;
    }

    sort(v.begin(), v.end());

    for(int i = 0; i + 2 < (int)v.size(); i++){
        if(v[i + 1] - v[i] <= v.back() - v[i + 1]){
            return true;
        }
    }

    return false;
}

int main(){

    int n;
    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> v[i];
    }

    AINT::build(1, 1, n);

    int q;
    cin >> q;

    while(q--){
        int l, r;
        cin >> l >> r;

        vector <int> aux; // max log elemente???
        while(!ok(aux)){
            int x = AINT::query(1, 1, n, l, r).second;
            AINT::update(1, 1, n, x, 0);
            aux.push_back(x);
        }
        sort(aux.begin(), aux.end());

        int sz = (int)aux.size();
        vector <int> maxi(sz, 0);

        maxi[sz - 1] = v[aux[sz - 1]];
        for(int i = sz - 2; i >= 0; i--){
            maxi[i] = max(maxi[i + 1], v[aux[i]]);
        }

        int ans = 0;
        for(int i = 0; i + 2 < sz; i++){
            int k = i + 2;
            for(int j = i + 1; j + 1 < sz; j++){
                while((k + 1 < sz) && (k < j || aux[k] - aux[j] < aux[j] - aux[i])){
                    ++k;
                }

                if(k > j && aux[k] - aux[j] >= aux[j] - aux[i]){
                    ans = max(ans, v[aux[i]] + v[aux[j]] + maxi[k]);
                }
            }
        }

        cout << ans << '\n';

        for(int x : aux){
            AINT::update(1, 1, n, x, v[x]);
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}

/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/

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