Submission #90852

#	Time	Username	Problem	Language	Result	Execution time	Memory
90852		MohamedAhmed0	Vudu (COCI15_vudu)	C++14	140 / 140	714 ms	44212 KiB

vudu

/* 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 (stderr)

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)
                     ~~^~~~~~~~~~~

• Subtask 1: 140 / 140