# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
94484 |
2019-01-19T10:04:53 Z |
theknife2001 |
Vudu (COCI15_vudu) |
C++11 |
|
1000 ms |
65772 KB |
#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
using namespace std;
unordered_map < ll , int > mp;
const int N=1e6+55;
int tree[N];
ll sum[N];
ll a[N];
int n;
int query(int x)
{
if(x<=0)
return 0;
return query(x-(x&(-x)))+tree[x];
}
void update(int x)
{
if(x>n)
return ;
tree[x]++;
update(x+(x&(-x)));
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int p;
cin>>p;
for(int i=n-1;i>=0;i--)
{
sum[i]=a[i]-p;
if(i!=n-1)
sum[i]+=sum[i+1];
a[i]=sum[i];
}
sort(a,a+n);
int cnt=1;
for(int i=0;i<n;i++)
{
if(mp[a[i]]==0)
mp[a[i]]=cnt++;
}
ll ans=0;
for(int i=n-1;i>=0;i--)
{
if(sum[i]>=0)
ans++;
ans+=query(mp[sum[i]]);
update(mp[sum[i]]);
}
cout<<ans<<endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
888 KB |
Output is correct |
2 |
Correct |
4 ms |
632 KB |
Output is correct |
3 |
Correct |
4 ms |
760 KB |
Output is correct |
4 |
Execution timed out |
1077 ms |
65340 KB |
Time limit exceeded |
5 |
Correct |
562 ms |
35284 KB |
Output is correct |
6 |
Execution timed out |
1035 ms |
51060 KB |
Time limit exceeded |
7 |
Execution timed out |
1080 ms |
52936 KB |
Time limit exceeded |
8 |
Execution timed out |
1068 ms |
46892 KB |
Time limit exceeded |
9 |
Execution timed out |
1089 ms |
65772 KB |
Time limit exceeded |
10 |
Correct |
955 ms |
51660 KB |
Output is correct |