oj.uz

Submission #90849

# Submission time Handle Problem Language Result Execution time Memory
90849 2018-12-24T19:58:19 Z MohamedAhmed0 Vudu (COCI15_vudu) C++14
140 / 140
 668 ms 40628 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 4 ms 792 KB Output is correct
4 Correct 668 ms 39844 KB Output is correct
5 Correct 345 ms 39844 KB Output is correct
6 Correct 570 ms 39844 KB Output is correct
7 Correct 534 ms 39844 KB Output is correct
8 Correct 484 ms 39844 KB Output is correct
9 Correct 581 ms 40628 KB Output is correct
10 Correct 518 ms 40628 KB Output is correct