/* Author : Mohamed Ahmed (CF : MohamedAhmed04)
since we need to know number of subarrays that their average is >= p
then let l be length of subarray then l * sum >= p then if we subtract
p from all elements then we need to know number of sub arrays that sum >= 0
so now problem transformed to know number of prev subarrays that their sum <= current sum
so we can use segment tree or Binary Indexed tree (fenwick tree) to find sum of elements
but we have one problem....values can be very large so we need to compress values so first we
will compress and after that everytime we will add to answer number of sub arrays <= arr[i] and
update in tree arr[i] (increase number of occurences of it).
*/
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6+5 ;
long long tree[4*MAX] ;
void update(int node , int l , int r , int idx)
{
if(l > idx || r < idx)
return ;
if(l == r)
{
tree[node]++;
return ;
}
long long mid = (l + r) >> 1 ;
update(node << 1 , l , mid , idx);
update(node << 1 | 1 , mid + 1 , r , idx) ;
tree[node] = tree[node << 1] + tree[node << 1 | 1] ;
}
long long query(int node , int l , int r , int from , int to)
{
if(from > r || to < l)
return 0 ;
if(l >= from && r <= to)
return tree[node] ;
long long mid = (l + r) >> 1 ;
long long x = query(node << 1 , l , mid , from , to) ;
long long y = query(node << 1 | 1 , mid + 1 , r , from , to);
return x+y ;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
long long n ;
cin>>n ;
long long arr[n+1] ;
for(int i = 1 ; i <= n ; ++i)
cin>>arr[i] ;
long long p ;
cin>>p ;
long long ans = 0 , sum = 0;
vector< pair<long long , long long> >vp ;
vp.push_back({0 , 0});
for(int i = 1 ; i <= n ; ++i)
{
sum += (arr[i] - p) ;
vp.push_back({sum , i});
}
sort(vp.begin() , vp.end());
long long idx = 0 ;
for(int i = 0 ; i < vp.size() ; ++i)
{
if(i != 0)
{
if(vp[i].first == vp[i-1].first)
--idx;
}
arr[vp[i].second] = idx;
idx++;
}
update(1 , 0 , n , arr[0]);
for(int i = 1 ; i <= n ; ++i)
{
ans += query(1 , 0 , n , 0 , arr[i]) * 1ll;
update(1 , 0 , n , arr[i]);
}
return cout<<ans , 0 ;
}
Compilation message
vudu.cpp: In function 'int main()':
vudu.cpp:67:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < vp.size() ; ++i)
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
760 KB |
Output is correct |
| 2 |
Correct |
4 ms |
920 KB |
Output is correct |
| 3 |
Correct |
4 ms |
920 KB |
Output is correct |
| 4 |
Correct |
714 ms |
41964 KB |
Output is correct |
| 5 |
Correct |
349 ms |
41964 KB |
Output is correct |
| 6 |
Correct |
572 ms |
41964 KB |
Output is correct |
| 7 |
Correct |
561 ms |
41964 KB |
Output is correct |
| 8 |
Correct |
515 ms |
41964 KB |
Output is correct |
| 9 |
Correct |
636 ms |
44212 KB |
Output is correct |
| 10 |
Correct |
556 ms |
44212 KB |
Output is correct |
