1879 2022. 12. 06 21:30:59 TomaSajt Inverzió cpp17 Elfogadva 50/50 287ms 19328 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 Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1696 KiB
2 Elfogadva 0/0 18ms 3264 KiB
3 Elfogadva 1/1 2ms 2284 KiB
4 Elfogadva 2/2 2ms 2340 KiB
5 Elfogadva 7/7 2ms 2492 KiB
6 Elfogadva 2/2 25ms 4024 KiB
7 Elfogadva 2/2 193ms 18488 KiB
8 Elfogadva 2/2 282ms 18324 KiB
9 Elfogadva 2/2 287ms 18576 KiB
10 Elfogadva 2/2 273ms 18900 KiB
11 Elfogadva 2/2 275ms 19104 KiB
12 Elfogadva 2/2 270ms 18656 KiB
13 Elfogadva 2/2 275ms 19028 KiB
14 Elfogadva 2/2 275ms 18932 KiB
15 Elfogadva 2/2 193ms 19068 KiB
16 Elfogadva 2/2 277ms 19068 KiB
17 Elfogadva 2/2 277ms 19068 KiB
18 Elfogadva 2/2 275ms 19064 KiB
19 Elfogadva 3/3 193ms 19068 KiB
20 Elfogadva 3/3 193ms 19320 KiB
21 Elfogadva 2/2 194ms 19272 KiB
22 Elfogadva 2/2 273ms 19272 KiB
23 Elfogadva 2/2 277ms 19328 KiB
24 Elfogadva 2/2 184ms 19276 KiB