oj.uz

답안 #90852

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90852 2018-12-24T20:07:45 Z MohamedAhmed0 Vudu (COCI15_vudu) C++14
140 / 140
 714 ms 44212 KB 
/* 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)
                     ~~^~~~~~~~~~~

Subtask #1
140.0 / 140.0

# 결과 실행 시간 메모리 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