18772022-12-06 21:29:13TomaSajtInverziócpp17Hibás válasz 31/50351ms20676 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, 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);
    }
    cout << sj + 1 << ' ' << si + 1;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base31/50
1Hibás válasz0/03ms1828 KiB
2Hibás válasz0/025ms3516 KiB
3Hibás válasz0/12ms2224 KiB
4Elfogadva2/22ms2448 KiB
5Elfogadva7/72ms2652 KiB
6Hibás válasz0/230ms4296 KiB
7Elfogadva2/2261ms18668 KiB
8Elfogadva2/2345ms18868 KiB
9Elfogadva2/2351ms19200 KiB
10Elfogadva2/2340ms19032 KiB
11Elfogadva2/2344ms19284 KiB
12Hibás válasz0/2333ms18964 KiB
13Hibás válasz0/2342ms19692 KiB
14Hibás válasz0/2344ms20008 KiB
15Hibás válasz0/2261ms19948 KiB
16Elfogadva2/2344ms20096 KiB
17Elfogadva2/2345ms20304 KiB
18Elfogadva2/2342ms20252 KiB
19Hibás válasz0/3261ms20504 KiB
20Hibás válasz0/3261ms20564 KiB
21Elfogadva2/2261ms20512 KiB
22Elfogadva2/2342ms20580 KiB
23Elfogadva2/2347ms20556 KiB
24Hibás válasz0/2250ms20676 KiB