1878 2022. 12. 06 21:30:02 TomaSajt Inverzió cpp17 Elfogadva 50/50 354ms 19844 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1860 KiB
2 Elfogadva 0/0 25ms 3556 KiB
3 Elfogadva 1/1 2ms 2292 KiB
4 Elfogadva 2/2 2ms 2552 KiB
5 Elfogadva 7/7 3ms 2876 KiB
6 Elfogadva 2/2 29ms 4376 KiB
7 Elfogadva 2/2 259ms 18668 KiB
8 Elfogadva 2/2 345ms 18800 KiB
9 Elfogadva 2/2 354ms 18748 KiB
10 Elfogadva 2/2 344ms 18644 KiB
11 Elfogadva 2/2 340ms 18960 KiB
12 Elfogadva 2/2 335ms 18448 KiB
13 Elfogadva 2/2 340ms 18932 KiB
14 Elfogadva 2/2 342ms 19096 KiB
15 Elfogadva 2/2 259ms 19048 KiB
16 Elfogadva 2/2 349ms 19272 KiB
17 Elfogadva 2/2 344ms 19188 KiB
18 Elfogadva 2/2 342ms 19444 KiB
19 Elfogadva 3/3 259ms 19516 KiB
20 Elfogadva 3/3 257ms 19520 KiB
21 Elfogadva 2/2 259ms 19584 KiB
22 Elfogadva 2/2 344ms 19584 KiB
23 Elfogadva 2/2 354ms 19584 KiB
24 Elfogadva 2/2 250ms 19844 KiB