18792022-12-06 21:30:59TomaSajtInverziócpp17Accepted 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/03ms1696 KiB
2Accepted0/018ms3264 KiB
3Accepted1/12ms2284 KiB
4Accepted2/22ms2340 KiB
5Accepted7/72ms2492 KiB
6Accepted2/225ms4024 KiB
7Accepted2/2193ms18488 KiB
8Accepted2/2282ms18324 KiB
9Accepted2/2287ms18576 KiB
10Accepted2/2273ms18900 KiB
11Accepted2/2275ms19104 KiB
12Accepted2/2270ms18656 KiB
13Accepted2/2275ms19028 KiB
14Accepted2/2275ms18932 KiB
15Accepted2/2193ms19068 KiB
16Accepted2/2277ms19068 KiB
17Accepted2/2277ms19068 KiB
18Accepted2/2275ms19064 KiB
19Accepted3/3193ms19068 KiB
20Accepted3/3193ms19320 KiB
21Accepted2/2194ms19272 KiB
22Accepted2/2273ms19272 KiB
23Accepted2/2277ms19328 KiB
24Accepted2/2184ms19276 KiB