8
1
2016
0

[BZOJ1303] [CQOI2009]中位数图

排序完了直接统计就好

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N=100005;
 
int n,a[N],b,c[N],d[10*N],e[10*N],pos,ans;
 
void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
int main(){
freopen("1303.in","r",stdin);
freopen("1303.out","w",stdout);
Read(n);Read(b);
for(int i=1;i<=n;i++){Read(a[i]);if(a[i]==b)pos=i,a[i]=0;else a[i]=a[i]>b?1:-1;}
d[n]=1;e[n]=1;
for(int i=pos-1;i;i--){c[i]=c[i+1]+a[i];d[c[i]+n]++;}
for(int i=pos+1;i<=n;i++){c[i]=c[i-1]+a[i];e[c[i]+n]++;}
for(int i=0;i<=2*n-1;i++)ans+=d[i]*e[2*n-i];
printf("%d\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 613

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com