首页 > 代码库 > bzoj1303: [CQOI2009]中位数图
bzoj1303: [CQOI2009]中位数图
bzoj1303: [CQOI2009]中位数图
代码如下:
1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 typedef long long ll; 8 inline void read(int &x){ 9 x=0;char ch;bool flag = false; 10 while(ch=getchar(),ch<‘!‘);if(ch == ‘-‘) ch=getchar(),flag = true; 11 while(x=10*x+ch-‘0‘,ch=getchar(),ch>‘!‘);if(flag) x=-x; 12 } 13 inline int cat_max(const int &a,const int &b){return a>b ? a:b;} 14 inline int cat_min(const int &a,const int &b){return a<b ? a:b;} 15 const int maxn = 1000010; 16 #define f(x) (x == m ? 0 : (x < m ? -1 : 1) ) 17 int a[maxn],l[maxn],r[maxn]; 18 int s[maxn]; 19 int main(){ 20 21 int n,m;read(n);read(m); 22 int p = -1; 23 for(int i=1,x;i<=n;++i){ 24 read(x);a[i] = f(x); 25 if(a[i] == 0) p = i; 26 } 27 for(int i=p-1;i>=1;--i) s[i] = a[i] + s[i+1],++l[s[i]+n]; 28 for(int i=p+1;i<=n;++i) s[i] = a[i] + s[i-1],++r[s[i]+n]; 29 int ans = 0;++l[n];++r[n]; 30 for(int i=0;i<(n<<1);++i) ans += l[i]*r[(n<<1)-i]; 31 printf("%d\n",ans); 32 //getchar();getchar(); 33 return 0; 34 }
bzoj1303: [CQOI2009]中位数图
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。