Desk Ordering ois

Aiuto
1

Mi sbaglia 2 output e mi fa 60 punti, l’idea e semplice. Faccio un segment tree in cui tengo in ogni nodo i 2 valori piu’ grandi, e poi faccio nel caso peggiore N chiamate in cui prendi questi massimi e vedo il minimo. Con complessita N log N, per qualche assurdo motivo mi sbaglia l’ultimo output ed uno della 3 subtask. Consigli su cosa potrebbe essere?

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct segtree
{
    int size;
    vector<pair<int, int>> maxs;

    void init(int n)
    {
        size = 1;
        while (size < n)
            size *= 2;
        maxs.resize(2 * size);
    }

    void build(vector<int> &V, int nodo, int lx, int rx)
    {
        if (rx - lx == 1)
        {
            if (lx < V.size())
            {
                maxs[nodo].first = V[lx];
                maxs[nodo].second = 0;
            }
            return;
        }

        int middle = (lx + rx) / 2;
        build(V, 2 * nodo + 1, lx, middle);
        build(V, 2 * nodo + 2, middle, rx);
        int a = maxs[2 * nodo + 1].first, b = maxs[2 * nodo + 1].second,
        c = maxs[2 * nodo + 2].first, d = maxs[2 * nodo + 2].second;
        int control = controllo(a, b, c, d);
        int control1 = 0;
        if(control == a) control1 = controllo(b, c, d);
        else if(control == b) control1 = controllo(a, c, d);
        else if(control == c) control1 = controllo(a, b, d);
        else control1 = controllo(a, b, c);
        maxs[nodo] = make_pair(control, control1);
    }

    void build(vector<int> &V)
    {
        build(V, 0, 0, size);
    }

    int controllo(int a, int b, int c, int d) {
        return max(a, max(b, max(c, d)));
    }

    int controllo(int a, int b, int c) {
        return max(a, max(b, c));
    }

    pair<int, int> massimo(int l, int r, int nodo, int lx, int rx)
    {
        if (lx >= r || l >= rx)
            return {0, 0};
        if (lx >= l && rx <= r)
            return maxs[nodo];
        int middle = (lx + rx) / 2;

        pair<int, int> sinistra = massimo(l, r, 2 * nodo + 1, lx, middle);
        pair<int, int> destra = massimo(l, r, 2 * nodo + 2, middle, rx);
        int a = sinistra.first, b = sinistra.second, c = destra.first, d = destra.second;
        int control = controllo(a, b, c, d);
        int control1 = 0;
        if(control == a) control1 = controllo(b, c, d);
        else if(control == b) control1 = controllo(a, c, d);
        else if(control == c) control1 = controllo(a, b, d);
        else control1 = controllo(a, b, c);
        
        return make_pair(control, control1);
    }

    pair<int, int> massimo(int l, int r)
    {
        return massimo(l, r, 0, 0, size);
    }
};

int main()
{
    int N, L;
    cin >> N >> L;

    segtree st;
    st.init(N);

    vector<int> V(N);

    for (int i = 0; i < N; ++i)
        cin >> V[i];

    if(N == 1) {
        cout << '0' << '\n';
    }

    st.build(V);

    int ans = INT32_MAX, a, b;
    pair<int, int> tmp;
    for(int i = 0; i + L <= N; ++i) {
        tmp = st.massimo(i, i + L + 1);
        ans = min(ans, tmp.first - tmp.second);
        // cout << tmp.first << ' ' << tmp.second << '\n';
    }

    cout << (ans / 2) << '\n';
    return 0;
}
2

Ciao,
l’idea e’ corretta, infatti devi applicare solo una piccola modifica al tuo codice per prendere 100. Ti consiglio di ricontrollare come includi o escludi gli estremi dell’intervallo considerato nella funzione massimo.

1 Mi Piace
3

alla fine era tutto per un semplice +1 :laughing: