18792022-12-06 21:30:59TomaSajtInverziócpp17Elfogadva 50/50287ms19328 KiB
#include <bits/stdc++.h>
#define speed ios::sync_with_stdio(0);cin.tie(0)
using namespace std;

struct segtree {
    int size;
    vector<int> data;
    segtree(int size) : size(size), data(4 * size, INT_MAX) {}
    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }
    void set(int i, int v, int x, int lx, int rx) {
        if (lx + 1 == rx) {
            data[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m) set(i, v, 2 * x + 1, lx, m);
        else set(i, v, 2 * x + 2, m, rx);
        data[x] = min(data[2 * x + 1], data[2 * x + 2]);
    }
    int get(int l, int r) {
        return get(l, r, 0, 0, size);
    }
    int get(int l, int r, int x, int lx, int rx) {
        if (rx <= l || r <= lx) return INT_MAX;
        if (l <= lx && rx <= r) return data[x];
        int m = (lx + rx) / 2;
        return min(get(l, r, 2 * x + 1, lx, m), get(l, r, 2 * x + 2, m, rx));
    }
};

int main() {
    speed;
    int n;
    cin >> n;
    segtree st(n);
    int s = -1, si, sj;
    for (int i = 0; i < n; i++) {
        int a; cin >> a; a--;
        int j = st.get(a, n);
        if (j != INT_MAX) {
            if (i - j > s) {
                s = i - j;
                si = i;
                sj = j;
            }
        }
        st.set(a, i);
    }
    if (s == -1) cout << "-1";
    else cout << sj + 1 << ' ' << si + 1;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/03ms1696 KiB
2Elfogadva0/018ms3264 KiB
3Elfogadva1/12ms2284 KiB
4Elfogadva2/22ms2340 KiB
5Elfogadva7/72ms2492 KiB
6Elfogadva2/225ms4024 KiB
7Elfogadva2/2193ms18488 KiB
8Elfogadva2/2282ms18324 KiB
9Elfogadva2/2287ms18576 KiB
10Elfogadva2/2273ms18900 KiB
11Elfogadva2/2275ms19104 KiB
12Elfogadva2/2270ms18656 KiB
13Elfogadva2/2275ms19028 KiB
14Elfogadva2/2275ms18932 KiB
15Elfogadva2/2193ms19068 KiB
16Elfogadva2/2277ms19068 KiB
17Elfogadva2/2277ms19068 KiB
18Elfogadva2/2275ms19064 KiB
19Elfogadva3/3193ms19068 KiB
20Elfogadva3/3193ms19320 KiB
21Elfogadva2/2194ms19272 KiB
22Elfogadva2/2273ms19272 KiB
23Elfogadva2/2277ms19328 KiB
24Elfogadva2/2184ms19276 KiB