Submission #1181882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181882		ytuzun	Mountains (NOI20_mountains)	C++20	100 / 100	196 ms	9808 KiB

Mountains

#include <iostream>
#include <vector>
#include <algorithm>

class FenwickTree {
private:
    std::vector<int> tree;
    int n;

public:
    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    void update(int index, int value) {
        index++;
        while (index <= n) {
            tree[index] += value;
            index += (index & -index);
        }
    }

    int query(int index) {
        index++;
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= (index & -index);
        }
        return sum;
    }
};

int main() {
    int n;
    std::cin >> n;
    std::vector<long long> heights(n);

    for (int i = 0; i < n; ++i) {
        std::cin >> heights[i];
    }

    // Koordinat Sıkıştırma
    std::vector<long long> compressedHeights = heights;
    std::sort(compressedHeights.begin(), compressedHeights.end());
    compressedHeights.erase(std::unique(compressedHeights.begin(), compressedHeights.end()), compressedHeights.end());

    for (int i = 0; i < n; ++i) {
        heights[i] = std::lower_bound(compressedHeights.begin(), compressedHeights.end(), heights[i]) - compressedHeights.begin();
    }

    long long result = 0;
    FenwickTree leftTree(n);
    FenwickTree rightTree(n);
    std::vector<int> leftCounts(n);
    std::vector<int> rightCounts(n);

    // L_y değerlerini hesapla
    for (int y = 0; y < n; ++y) {
        leftCounts[y] = leftTree.query(heights[y] - 1);
        leftTree.update(heights[y], 1);
    }

    // R_y değerlerini hesapla
    for (int y = n - 1; y >= 0; --y) {
        rightCounts[y] = rightTree.query(heights[y] - 1);
        rightTree.update(heights[y], 1);
    }

    // Sonucu hesapla
    for (int y = 1; y < n - 1; ++y) {
        result += (long long)leftCounts[y] * rightCounts[y];
    }

    std::cout << result << std::endl; // Sonucu yazdır

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12