131332025-01-06 17:50:09simon0219Inverziócpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
base3/50
1Wrong answer0/01ms508 KiB
2Wrong answer0/020ms1196 KiB
3Accepted1/11ms316 KiB
4Wrong answer0/21ms316 KiB
5Wrong answer0/71ms316 KiB
6Wrong answer0/224ms1244 KiB
7Wrong answer0/2224ms8104 KiB
8Wrong answer0/2266ms8088 KiB
9Wrong answer0/2268ms8104 KiB
10Wrong answer0/2263ms8088 KiB
11Wrong answer0/2261ms8104 KiB
12Wrong answer0/2259ms8088 KiB
13Wrong answer0/2263ms8088 KiB
14Wrong answer0/2263ms8200 KiB
15Wrong answer0/2222ms8088 KiB
16Wrong answer0/2263ms8096 KiB
17Wrong answer0/2263ms8100 KiB
18Wrong answer0/2261ms8104 KiB
19Wrong answer0/3223ms8092 KiB
20Wrong answer0/3223ms8080 KiB
21Wrong answer0/2224ms8092 KiB
22Wrong answer0/2266ms8104 KiB
23Wrong answer0/2261ms8088 KiB
24Accepted2/2209ms8088 KiB