[USACO 2017 Jan G]Balanced Photo

NC24051. [USACO 2017 Jan G]Balanced Photo

描述

Farmer John is arranging his N cows in a line to take a photo ( $1 \leq N \leq 100,000$ ). The height of the ith cow in sequence is $h_i$ , and the heights of all cows are distinct.

As with all photographs of his cows, FJ wants this one to come out looking as nice as possible. He decides that cow i looks "unbalanced" if $L_i$ and $R_i$ differ by more than factor of 2, where $L_i$ and $R_i$ are the number of cows taller than i on her left and right, respectively. That is, i is unbalanced if the larger of $L_i$ and $R_i$ is strictly more than twice the smaller of these two numbers. FJ is hoping that not too many of his cows are unbalanced.

Please help FJ compute the total number of unbalanced cows.

输入描述

The first line of input contains N. The next N lines contain , each a nonnegative integer at most 1,000,000,000.

输出描述

Please output a count of the number of cows that are unbalanced.

示例1

输入:

输出:

说明:

In this example, the cows of heights 34, 5, and 2 are unbalanced.

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 40ms, 内存消耗: 2672K, 提交时间: 2020-12-12 09:47:49

#include<bits/stdc++.h>
using namespace std;
struct node{
	int val,num;
}e[200000];
long long sum[200000],n,a[200000],after[200000];
void ad(int x,int k){
	while(x<=n){
		sum[x]+=k;
		x+=x&(-x);
	}
}
int q(int x){
	int res=0;
	while(x>=1){
		res+=sum[x];
		x-=x&(-x);
	}
	return res;
} 
bool cmp(node x,node y){
	return x.val>y.val;
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&e[i].val);
		e[i].num=i;
	}
	sort(e+1,e+1+n,cmp);
	for(int i=1;i<=n;i++){
		after[e[i].num]=i;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		int l=q(after[i]);
		int r=after[i]-l-1;
		if((l*2<r)||(r*2<l))ans++;
		ad(after[i],1);
	}
	cout<<ans<<endl;
}