Submission #90849

#	Time	Username	Problem	Language	Result	Execution time	Memory
90849		MohamedAhmed0	Vudu (COCI15_vudu)	C++14	140 / 140	668 ms	40628 KiB

vudu

#include <bits/stdc++.h>

using namespace std;

const long long MAX = 1e6+5 ;
long long tree[8*MAX] ;

void update(long long node , long long l , long long r , long long 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(long long node , long long l , long long r , long long from , long long 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(long long 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(long long i = 1 ; i <= n ; ++i)
    {
        sum += (arr[i] - p) ;
        vp.push_back({sum , i});
    }
    sort(vp.begin() , vp.end());
    long long idx = 0 ;
    for(long long 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(long long 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:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i = 0 ; i < vp.size() ; ++i)
                           ~~^~~~~~~~~~~

• Subtask 1: 140 / 140