6. 小埋的解密游戏
题目ID：15880必做题100分
最新提交：
Wrong Answer
10 分
历史最高：
Wrong Answer
10 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
小埋最近在玩一个解密游戏，这个游戏会提供 nn 个数。
我们需要求出：在这 nn 个数里面，有多少个连续的数的平均数大于某个给定的数 MM 。
这个数量可能会很大，所以我们要输出这个数对 10000000071000000007 的取模结果。
请你帮小埋求出结果。
输入格式
输入有两行。第一行为两个数 nn 和 MM 。第二行为 nn 个数。
输出格式
输出的数占一行，即问题的解对 10000000071000000007 取模的结果。
样例
Input 1
4 3 1 5 4 2
Output 1
5
Input 2
4 4 5 2 7 3
Output 2
6
样例解释
对于测试样例1，对于这4个数，有 5 组数字符合要求：{1,5,4}，{5}，{5,4}，{5,4,2}，{4}。
数据范围
1<=n<=2∗1051<=n<=2∗105
1<M<=3∗1031<M<=3∗103
所有的数均为正整数且不大于500
WA代码：
#include <bits/stdc++.h>
using namespace std;
long long n,q,temp,t,t1,t2,cnt = 0,m,b[200001];
struct node
{
long long id;
long long s;
}a[200001];
bool cmp1(node a,node b)
{
return a.id<b.id;
}
bool cmp2(node a,node b)
{
if(a.s==b.s)
return cmp1(a,b);
return a.s<b.s;
}
long long low_bit(long long x)
{
return x & (-x);
}
void add(long long p,long long num)
{
while(p<=n)
{
b[p] += num;
p += low_bit(p);
}
}
long long ask(long long p)
{
long long num = 0;
while(p!=0)
{
num += b[p];
p -= low_bit(p);
}
return num;
}
int main()
{
cin>>n>>m;
a[0].s = 0;
for(int i = 1;i <= n;i++)
{
cin>>t;
t-=m;
a[i].s = a[i-1].s+t;
a[i].id = i;
}
sort(a+1,a+1+n,cmp2);
for(int i = 1,d = 1;i <= n;i++,d++)
{
// if(i>1&&a[i].s==a[i-1].s)
// d--;
a[i].s = d;
}
sort(a+1,a+1+n,cmp1);
for(int i = 1;i <= n;i++)
{
add(a[i].s,1);
cnt+=ask(a[i].s);
cnt%=1000000007;
}
cout<<cnt;
return 0;
}
T1 比正解少 1
T2 对的
T3 比正解多 2
其他都错的
555……