Submission #761995

#	Time	Username	Problem	Language	Result	Execution time	Memory
761995		KN200711	Mountains (NOI20_mountains)	C++14	100 / 100	363 ms	34020 KiB

Mountains

# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
using namespace std;

const int MXN = 3e5;
ll fen[300001];
map<ll, int> M;

void upd(int a) {
	while(a <= MXN) {
		fen[a]++;
		a += a&(-a);
	}
	return;
}

ll qry(int a) {
	int res = 0;
	while(a > 0) {
		res += fen[a];
		a -= a&(-a);
	}
	return res;
}

int main() {
	int N;
	scanf("%d", &N);
	
	vector<ll> arr(N);
	for(int i=0;i<N;i++) {
		scanf("%lld", &arr[i]);
		M[arr[i]] = 1;
	}
	int cnt = 1;
	for(auto p : M) {
		M[p.fi] = cnt;
		cnt++;
	}
	for(int i=0;i<N;i++) {
		arr[i] = M[arr[i]];
	//	cout<<arr[i]<<endl;
	}
	
	vector<ll> pref(N);
	for(int i=0;i<N;i++) {
		pref[i] = qry(arr[i] - 1);
		upd(arr[i]);
	}
	
	ll ans = 0ll;
	
	for(int i=0;i<=MXN;i++) fen[i] = 0;
	vector<ll> suff(N);
	for(int i=N-1;i>=0;i--) {
		suff[i] = qry(arr[i] - 1);
		upd(arr[i]);
		
	//	cout<<pref[i]<<" "<<suff[i]<<endl;
		
		ans += (1ll * pref[i]) * (1ll * suff[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

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