Submission #1181902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181902		den1z19	Mountains (NOI20_mountains)	C++17	100 / 100	65 ms	8520 KiB

Mountains

#include "bits/stdc++.h"
using std::cout, std::cin, std::vector, std::string;
long long int left = 0, right = 0;
long long int n, tmp, count = 0;
long long int j, i, last = 0;
int indexx;

class FenwickTree {
private:
    vector<int> bit;
    int size;
    
public:
    FenwickTree(int n) {
        size = n;
        bit.assign(n + 1, 0);
    }
    
    void update(int idx, int val) {
        idx++; 
        while (idx <= size) {
            bit[idx] += val;
            idx += idx & -idx; 
        }
    }
    
    int query(int idx) {
        idx++; 
        int sum = 0;
        while (idx > 0) {
            sum += bit[idx];
            idx -= idx & -idx; 
        }
        return sum;
    }
    
    int countLessEqual(int idx) {
        return query(idx);
    }
    
    int insert(int element) {
        update(element, 1);
        return countLessEqual(element - 1);
    }
};

class FastSortedInsert {
private:
    FenwickTree ft;
    int maxSize;
    
public:
    FastSortedInsert(int maxSize = 200005) : ft(maxSize), maxSize(maxSize) {}
    
    int insert(int element) {
        return ft.insert(element);
    }
};

int insertSorted(vector<int>& freq, int value, int& multi) {
    freq[value]++;
    multi++;
    
    int position = 0;
    for (int i = 0; i < value; i++) {
        position += freq[i];
    }
    return position;
}

void solve() {
    cin >> n;
    FastSortedInsert si(n + 1);
    vector<std::pair<long long int, long long int>> h(n);
    std::vector<long long int> dp(n);
    
    for (long long int i = 0; i < n; i++) {
        cin >> h[i].first;
        h[i].second = i;
    }
    
    std::sort(h.begin(), h.end());
    int multi = 0;
    
    si.insert(h[0].second);
    multi++;
    si.insert(h[1].second);
    multi++;
    if (h[1].first != h[0].first) multi = 1;
    
    indexx = si.insert(h[2].second);
    multi++;
    if (h[2].first != h[1].first) multi = 1;
    
    left = std::max(0, indexx - multi + 1);
    right = 3 - multi - left;
    count = right * left;
    
    for (i = 3; i < n; i++) {
        left = right = 0;
        indexx = si.insert(h[i].second);
        multi++;
        if (h[i].first != h[i - 1].first) multi = 1;
        left = std::max(0, indexx - multi + 1);
        right = i + 1 - multi - left;
        count += right * left;
    }
    
    cout << count << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    unsigned long long ct = 1;
    // cin >> ct;
    while (ct--) solve();
}

• 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