Submission #253208

#	Time	Username	Problem	Language	Result	Execution time	Memory
253208		nandonathaniel	Mountains (NOI20_mountains)	C++14	100 / 100	150 ms	17896 KiB

Mountains

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=300005;

LL a[MAXN],bit[2][MAXN],MAX;

void update(LL now,LL val,LL no){
	for(LL i=now;i<=MAX;i+=(i&(-i)))bit[no][i]+=val;
}

LL query(LL now,LL no){
	LL ret=0;
	if(now==0)return ret;
	for(LL i=now;i>0;i-=(i&(-i)))ret+=bit[no][i];
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	LL n;
	cin >> n;
	vector<pii> v;
	for(LL i=1;i<=n;i++){
		cin >> a[i];
		v.push_back({a[i],i});
	}
	sort(v.begin(),v.end());
	for(LL i=0;i<v.size();i++){
		if(i==0 || v[i].first!=v[i-1].first)MAX++;
		a[v[i].second]=MAX;
	}
	for(LL i=1;i<=n;i++)update(a[i],1,1);
	LL ans=0;
	for(LL i=1;i<=n;i++){
		update(a[i],-1,1);
		ans+=query(a[i]-1,0)*query(a[i]-1,1);
		update(a[i],1,0);
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:30:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(LL i=0;i<v.size();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