Submission #1087900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087900		vuavisao	Mountains (NOI20_mountains)	C++14	100 / 100	129 ms	12504 KiB

Mountains

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 300'000 + 10;

struct FenWick {
	int n_node = 0;
	vector<int> tree = {};

	void resize(int n) { n_node = n; tree.resize(n + 10, 0); }
	FenWick() {};
	FenWick(int n) { this -> resize(n); };

	void Update(int idx, int val) {
		for( ; idx <= n_node; idx += (idx & - idx)) tree[idx] += val;
		return;
	}

	int Query(int idx) {
		int res = 0;
		for( ; idx > 0; idx -= (idx & - idx)) res += tree[idx];
		return res;
	}

	int Sum_to(int l, int r) {
		if(l > r) return 0;
		return Query(r) - Query(l - 1);
	}

	int kth(int val) {
		int res = 0, s = 0;
		for(int mask = 30; mask >= 0; -- mask) {
			int nxt = res | (1 << mask);
			if(nxt < n_node && s + tree[nxt] < val) {
				res = nxt;
				s += tree[nxt];
			}
		}
		++ res; return res;
	}

	void reset(int idx) {
		for ( ; idx <= n_node; idx += (idx & - idx)) tree[idx] = 0;
		return;
	}
};

int n;
ll a[N];

int L[N], R[N];

void compress() {
	vector<ll> Pos = {};
	for (int i = 1; i <= n; ++ i) {
		Pos.push_back(a[i]);
	}
	
	sort(Pos.begin(), Pos.end());
	Pos.resize(unique(Pos.begin(), Pos.end()) - Pos.begin());

	for (int i = 1; i <= n; ++ i) {
		a[i] = lower_bound(Pos.begin(), Pos.end(), a[i]) - Pos.begin() + 1;
	}
}

void calc(int cnt[]) {
	FenWick bit(n);
	for (int i = 1; i <= n; ++ i) {
		cnt[i] = bit.Query(a[i]);
		bit.Update(a[i] + 1, 1);
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++ i) cin >> a[i];
	compress();
	calc(L);
	reverse(a + 1, a + 1 + n);
	calc(R);
	ll res = 0;
	for (int i = 1; i <= n; ++ i) res += 1ll * L[i] * R[n - i + 1];
	cout << res;
	return (0 ^ 0);
}

/// Code by vuavisao

• 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