Submission #329921

#	Time	Username	Problem	Language	Result	Execution time	Memory
329921		M_W	Mountains (NOI20_mountains)	C++14	100 / 100	1016 ms	32864 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
map<long long, int> mp;
long long a[300300], b[300300];
int fwt[300300];

void add(int v){
	for(;v <= 300300; v += (v & -v))
		fwt[v]++;
}

int query(int v){
	int ret = 0;
	for(;v > 0; v -= (v & -v)){
		ret += fwt[v];
	}	
	return ret;
}

int main(){
	int N;
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		scanf("%lld", &a[i]);
		b[i] = a[i];
	}	
	
	sort(a, a + N);
	int k = 1;
	for(int i = 0; i < N; i++){
		if(mp[a[i]] == 0) mp[a[i]] = k++;
	}
	vector<int> l;
	for(int i = 0; i < N; i++){
		l.push_back(query(mp[b[i]] - 1));
		add(mp[b[i]]);
	}
	memset(fwt, 0, sizeof fwt);
	long long ans = 0;
	for(int i = N - 1; i >= 0; i--){
		ans += (query(mp[b[i]] - 1) * 1ll * l[i] * 1ll) * 1ll;
		add(mp[b[i]]);
	}
	printf("%lld", ans);
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Mountains.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%lld", &a[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