191022025-11-23 12:25:34algoproInverziócpp17Elfogadva 50/50145ms6500 KiB
// UUID: ca224b2b-aa45-4099-8332-904b528271f9
#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<int> t;
    SegTree(int _n=0) { init(_n); }
    void init(int _n) {
        n = 1;
        while (n < _n) n <<= 1;
        t.assign(2*n, 0); // tároljuk a maximum indexet (0 = nincs)
    }
    // pontfrissítés: állítsuk a pozíció pos értékét val-ra (max)
    void update(int pos, int val) {
        pos += n;
        t[pos] = max(t[pos], val);
        for (pos >>= 1; pos; pos >>= 1) t[pos] = max(t[pos<<1], t[(pos<<1)|1]);
    }
    // lekérdezés [l, r] inkluzív maximum
    int query(int l, int r) {
        if (l > r) return 0;
        l += n; r += n;
        int res = 0;
        while (l <= r) {
            if (l & 1) res = max(res, t[l++]);
            if (!(r & 1)) res = max(res, t[r--]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<int> a(N+1);
    for (int i = 1; i <= N; ++i) cin >> a[i];

    // Értékek 1..N (permutáció), szegmentfa indexeket tárol (maximum index ahol az adott értéket láttuk jobbról)
    SegTree st(N+5);
    long long bestDist = -1;
    int bi = -1, bj = -1;

    // megyünk jobbról balra; amikor i-nél vagyunk, a fa tartalmazza az összes j>i indexet
    for (int i = N; i >= 1; --i) {
        int val = a[i];
        // keresünk legnagyobb indexet olyan értékek között, amelyek kisebbek mint val: [1, val-1]
        if (val > 1) {
            int j = st.query(1, val-1);
            if (j > 0) {
                long long dist = (long long)j - i;
                if (dist > bestDist) {
                    bestDist = dist;
                    bi = i;
                    bj = j;
                }
            }
        }
        // frissítjük, hogy ezt a val értéket az i indexen láttuk
        st.update(val, i);
    }

    if (bestDist == -1) {
        cout << -1 << "\n";
    } else {
        cout << bi << " " << bj << "\n";
    }

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/01ms508 KiB
2Elfogadva0/012ms1076 KiB
3Elfogadva1/11ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva7/71ms316 KiB
6Elfogadva2/213ms1164 KiB
7Elfogadva2/2123ms6492 KiB
8Elfogadva2/2144ms6492 KiB
9Elfogadva2/2145ms6488 KiB
10Elfogadva2/2144ms6476 KiB
11Elfogadva2/2142ms6488 KiB
12Elfogadva2/2141ms6452 KiB
13Elfogadva2/2142ms6452 KiB
14Elfogadva2/2140ms6484 KiB
15Elfogadva2/2123ms6460 KiB
16Elfogadva2/2144ms6488 KiB
17Elfogadva2/2142ms6500 KiB
18Elfogadva2/2141ms6488 KiB
19Elfogadva3/3123ms6452 KiB
20Elfogadva3/3123ms6464 KiB
21Elfogadva2/2126ms6452 KiB
22Elfogadva2/2141ms6448 KiB
23Elfogadva2/2142ms6488 KiB
24Elfogadva2/2125ms6492 KiB