Submission #224031

#	Time	Username	Problem	Language	Result	Execution time	Memory
224031		crimsonred	Mountains (NOI20_mountains)	C++17	100 / 100	1751 ms	55520 KiB

Mountains

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

#define mod 1'000'000'007
typedef long long ll;

template<typename T>
void deb(initializer_list<T> l)
{
	for (auto &e : l)
		cout << e << ' ';
	cout << endl;
}

struct SegmentTree
{
	vector<ll> st;

	void build(vector<ll>& a, ll n)
	{
		st.resize(2 * n, 0);
		for (ll i = n; i < 2 * n; ++i)
			st[i] = a[i - n];
		for (ll i = n - 1; i > 0; --i)
			st[i] = st[2 * i] + st[2 * i + 1];
	}

	void update(ll idx, ll val, ll n)
	{
		idx += n;
		st[idx] += val;
		for (idx /= 2; idx; idx /= 2)
			st[idx] = st[2 * idx] + st[2 * idx + 1];
	}

	ll query(ll left, ll right, ll n)
	{
		left += n;
		right += n;
		ll sum = 0;
		while (left < right)
		{
			if (left % 2 == 1)
			{
				sum += st[left];
				++left;
			}
			if (right % 2 == 1)
			{
				--right;
				sum += st[right];
			}
			left /= 2;
			right /= 2;
		}
		return sum;
	}
};

void solve()
{
	ll n;
	cin >> n;
	vector<ll> a(n);
	set<ll> s;
	for (auto &e : a)
	{
		cin >> e;
		s.insert(e);
	}

	map<ll, ll> m;
	ll num = 0;
	for (auto &e : s)
		m[e] = num++;

	vector<ll> left(n, 0), right(n, 0);
	++left[m[a[0]]];
	for (ll i = 1; i < n; ++i)
		++right[m[a[i]]];

	SegmentTree l, r;
	l.build(left, n);
	r.build(right, n);

	ll ans = 0;
	for (ll i = 1; i < n - 1; ++i)
	{
		r.update(m[a[i]], -1, n);
		ans += l.query(0, m[a[i]], n) * r.query(0, m[a[i]], n);
		l.update(m[a[i]], 1, n);
	}
	cout << ans << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	// cin >> t;
	while (t--)
		solve();

	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