Submission #676490

#	Time	Username	Problem	Language	Result	Execution time	Memory
676490		penguin133	Mountains (NOI20_mountains)	C++17	100 / 100	290 ms	19904 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<long long, int> >pq;
long long ft[300005];
long long in1[300005];
long long in2[300005];
int cnt2 = 1;
int ls(int x){
	return x & -x;
}
int query(int x){
	long long sum = 0;
	for(;x;x -= ls(x)){
		sum += ft[x];
	}
	return sum;
}

void update(int x, int v){
	for(;x<=cnt2;x += ls(x)){
		ft[x] += v;
	}
}
int main(){
	int n;
	cin >> n;
	long long cnt = 0;
	cnt2 = 1;

	pair<long long, int> d[n+1];
	long long c[n+1];
	for(int i=1;i<=n;i++){
		cin >> c[i];
	}
	for(int i = 1; i <= n; i++){
		d[i].first = c[i];
		d[i].second = i;
	}
	sort(d + 1, d + n + 1);
	
	for(int i = 1; i <= n; i++){
		if (i > 1 && d[i].first != d[i-1].first) cnt2++;
		c[d[i].second] = cnt2;
	}
	for(int i=1;i<=n;i++){
		in1[i] = query(c[i] - 1);
		update(c[i], 1);
	}
	fill(ft, ft + n + 1, 0);
	for(int i=n;i>=1;i--){
		in2[i] = query(c[i]-1);
		update(c[i], 1);
	}
	for(int i=0;i<n;i++){
		cnt += in1[i]*in2[i];
	}
	cout << cnt;
}

• 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