131332025-01-06 17:50:09simon0219Inverziócpp17Hibás válasz 3/50268ms8200 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Inversion {
    int index;
    int value;
};

int main() {
    int N;
    cin >> N;
    vector<int> S(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
    }

    pair<int, int> max_inversion(-1, -1);
    int max_distance = -1;
    vector<Inversion> inversions;

    // Párosítjuk a számokat az indexükkel, majd rendezzük az értékek szerint
    for (int i = 0; i < N; ++i) {
        inversions.push_back({i + 1, S[i]});
    }
    sort(inversions.begin(), inversions.end(), [](const Inversion& a, const Inversion& b) {
        return a.value < b.value;
    });

    vector<int> fenwick_tree(N + 1, 0);

    auto update = [&](int pos) {
        while (pos <= N) {
            fenwick_tree[pos] += 1;
            pos += pos & -pos;
        }
    };

    auto query = [&](int pos) {
        int sum = 0;
        while (pos > 0) {
            sum += fenwick_tree[pos];
            pos -= pos & -pos;
        }
        return sum;
    };

    for (int i = N - 1; i >= 0; --i) {
        int index = inversions[i].index;
        int inversion_count = query(index);
        if (inversion_count > 0) {
            int farthest = index + inversion_count;
            if (farthest <= N && farthest - index > max_distance) {
                max_distance = farthest - index;
                max_inversion = {index, farthest};
            }
        }
        update(index);
    }

    if (max_distance > 0) {
        cout << max_inversion.first << " " << max_inversion.second << endl;
    } else {
        cout << "-1" << endl;
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base3/50
1Hibás válasz0/01ms508 KiB
2Hibás válasz0/020ms1196 KiB
3Elfogadva1/11ms316 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/71ms316 KiB
6Hibás válasz0/224ms1244 KiB
7Hibás válasz0/2224ms8104 KiB
8Hibás válasz0/2266ms8088 KiB
9Hibás válasz0/2268ms8104 KiB
10Hibás válasz0/2263ms8088 KiB
11Hibás válasz0/2261ms8104 KiB
12Hibás válasz0/2259ms8088 KiB
13Hibás válasz0/2263ms8088 KiB
14Hibás válasz0/2263ms8200 KiB
15Hibás válasz0/2222ms8088 KiB
16Hibás válasz0/2263ms8096 KiB
17Hibás válasz0/2263ms8100 KiB
18Hibás válasz0/2261ms8104 KiB
19Hibás válasz0/3223ms8092 KiB
20Hibás válasz0/3223ms8080 KiB
21Hibás válasz0/2224ms8092 KiB
22Hibás válasz0/2266ms8104 KiB
23Hibás válasz0/2261ms8088 KiB
24Elfogadva2/2209ms8088 KiB