Submission #265368

#	Time	Username	Problem	Language	Result	Execution time	Memory
265368		T0p_	Mountains (NOI20_mountains)	C++14	100 / 100	409 ms	29684 KiB

Mountains

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

#define pb push_back

long long arr[300300], fw[2][300300];
vector<long long> v;
unordered_map<long long, int> com;

void update(int idx1, int idx2, int val)
{
	while(idx2 <= 300000)
	{
		fw[idx1][idx2] += val;
		idx2 += -idx2&idx2;
	}
}

long long query(int idx1, int idx2)
{
	long long ret = 0;
	while(idx2)
	{
		ret += fw[idx1][idx2];
		idx2 -= -idx2&idx2;
	}
	return ret;
}

int main()
{
	int n, sz = 0;
	long long ans = 0;
	scanf(" %d",&n);
	for(int i=1 ; i<=n ; i++)
	{
		scanf(" %lld",&arr[i]);
		v.push_back(arr[i]);
	}
	sort(v.begin(), v.end());
	for(int i=0 ; i<n ; i++)
		if(!com.count(v[i]))
			com[v[i]] = ++sz;
	for(int i=1 ; i<=n ; i++)
	{
		arr[i] = com[arr[i]];
		update(1, arr[i], 1);
	}
	for(int i=1 ; i<=n ; i++)
	{
		update(1, arr[i], -1);
		ans += query(0, arr[i]-1) * query(1, arr[i]-1);
		update(0, arr[i], 1);
	}
	printf("%lld\n",ans);
	return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  scanf(" %d",&n);
      |  ~~~~~^~~~~~~~~~
Mountains.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |   scanf(" %lld",&arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• 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