Submission #1268387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268387		aryan	Mountains (NOI20_mountains)	C++20	100 / 100	795 ms	26252 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;


using i64 = long long;

template <class T>
struct fenwick{
    int N;
    vector<T> tree;
    fenwick(int _n){
        N = _n;
        tree = vector<T>(N + 1);
    }
    void update(int i,T v){
        for(++ i;i <= N;i += (i & -i)){
            tree[i] += v;
        }
    }
    T query(int i){
        T val = 0;
        for(++ i;i > 0;i -= (i & -i)){
            val += tree[i];
        }
        return val;
    }
};



int main(){

    int n;
    cin >> n;
    vector<i64> h(n);
    for(i64 &e : h) cin >> e;

    vector<int> ind(n);
    iota(ind.begin(),ind.end(),0);
    sort(ind.begin(),ind.end(),[&](int i,int j){
        return h[i] < h[j];
    });



    map<i64,int> mp;
    for(int i = 0;i < n;i++){
        mp[h[ind[i]]] = i; 
    }

    vector<i64> ans(n,0);

    for(int p = 0;p <= 1;p++){
        fenwick<int> fen(n);
        for(int i = 0;i < n;i++){
            fen.update(mp[h[i]],1);        
            int tot = fen.query(mp[h[i]] - 1);
            if(p == 0) ans[i] = tot;
            if(p == 1) ans[n - i - 1] = (ans[n - i - 1] * 1LL * tot);
        }
        reverse(h.begin(),h.end());
    }

    i64 tot = 0;
    for(int i = 0;i < n;i++){
        tot += ans[i];
    }
    cout << tot << '\n';

    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