Submission #211478

#	Time	Username	Problem	Language	Result	Execution time	Memory
211478		popovicirobert	Mountains (NOI20_mountains)	C++14	100 / 100	117 ms	11896 KiB

Mountains

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lsb(x) (x & (-x))

using namespace std;

struct Fenwick {
    vector <int> aib;
    int n;
    Fenwick(int _n = 0) {
        n = _n;
        aib.resize(n + 1);
    }
    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }
    inline void update(int pos, int val) {
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }
    inline int query(int pos) {
        int ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }
    inline int sum(int l, int r) {
        return query(r) - query(l - 1);
    }
};

int main() {
#ifdef HOME
	ifstream cin("C.in");
	ofstream cout("C.out");
#endif
	int i, n;
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	vector<pair<ll, int>> h(n);
	for(i = 0; i < n; i++) {
		cin >> h[i].first;
		h[i].second = i + 1;
	}
	sort(h.begin(), h.end());
	Fenwick fen(n);
	ll ans = 0;
	i = 0;
	while(i < n) {
		int j = i;
		while(j < n && h[i].first == h[j].first) {
			int cur = fen.query(h[j].second);
			ans += 1LL * (i - cur) * cur;
			j++;
		}
		while(i < j) {
			fen.update(h[i].second, 1);
			i++;
		}
	}
	cout << ans;

	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