#pragma GCC optimize ("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define task "task"
#define task "task"
#define prll pair<ll,ll>
#define pb push_back
#define ld long double
const ll MIN=-1e18,MAX=1e18,MOD=1e9+7;
int tree[4000005];
int a[1000005];
vector<int> vc;
map<int,int> danh;
int d=0;
int ans=0;
void update(int node,int l,int r,int u)
{
if(l>u or r<u) return;
if(l==r)
{
tree[node]+=1;
return;
}
int m=(l+r)/2;
update(node*2,l,m,u);
update(node*2+1,m+1,r,u);
tree[node]=tree[node*2]+tree[node*2+1];
}
int get(int node,int l,int r,int u,int v)
{
if(l>v or r<u) return 0;
if(l>=u and r<=v) return tree[node];
int m=(l+r)/2;
return get(node*2,l,m,u,v)+get(node*2+1,m+1,r,u,v);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,p;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>p;
for(int i=1;i<=n;i++)
{
a[i]=a[i]+a[i-1]-p;
vc.push_back(a[i]);
}
vc.push_back(0);
sort(vc.begin(),vc.end());
for(auto i:vc)
{
if(!danh[i])
{
danh[i]=++d;
}
}
update(1,1,d,danh[0]);
for(int i=1;i<=n;i++)
{
int temp=--upper_bound(vc.begin(),vc.end(),a[i])-vc.begin();
if(temp<0) continue;
temp=danh[vc[temp]];
ans+=get(1,1,d,1,temp);
update(1,1,d,danh[a[i]]);
}
cout<<ans;
}
/*
-1 0 0
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
4 ms |
724 KB |
Output is correct |
| 3 |
Correct |
4 ms |
596 KB |
Output is correct |
| 4 |
Execution timed out |
1050 ms |
65536 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1010 ms |
43748 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1054 ms |
63672 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1066 ms |
65536 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1075 ms |
58228 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1040 ms |
65536 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1056 ms |
64408 KB |
Time limit exceeded |
