18782022-12-06 21:30:02TomaSajtInverziócpp17Accepted 50/50354ms19844 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 + 1);
    int s = -1, si, sj;
    for (int i = 0; i < n; i++) {
        int a; cin >> a; a--;
        int j = st.get(a, n - 1);
        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/03ms1860 KiB
2Accepted0/025ms3556 KiB
3Accepted1/12ms2292 KiB
4Accepted2/22ms2552 KiB
5Accepted7/73ms2876 KiB
6Accepted2/229ms4376 KiB
7Accepted2/2259ms18668 KiB
8Accepted2/2345ms18800 KiB
9Accepted2/2354ms18748 KiB
10Accepted2/2344ms18644 KiB
11Accepted2/2340ms18960 KiB
12Accepted2/2335ms18448 KiB
13Accepted2/2340ms18932 KiB
14Accepted2/2342ms19096 KiB
15Accepted2/2259ms19048 KiB
16Accepted2/2349ms19272 KiB
17Accepted2/2344ms19188 KiB
18Accepted2/2342ms19444 KiB
19Accepted3/3259ms19516 KiB
20Accepted3/3257ms19520 KiB
21Accepted2/2259ms19584 KiB
22Accepted2/2344ms19584 KiB
23Accepted2/2354ms19584 KiB
24Accepted2/2250ms19844 KiB