oj.uz

Submission #90847

# Submission time Handle Problem Language Result Execution time Memory
90847 2018-12-24T19:53:08 Z MohamedAhmed0 Vudu (COCI15_vudu) C++14
42 / 140
 1000 ms 42980 KB 
#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 ;
    }
    int 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] ;
}

int 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] ;
    int mid = (l + r) >> 1 ;
    int x = query(node << 1 , l , mid , from , to) ;
    int y = query(node << 1 | 1 , mid + 1 , r , from , to);
    return x+y ;
}

int main()
{
    int 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<int , int> >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:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < vp.size() ; ++i)
                     ~~^~~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 632 KB Output is correct
2 Correct 5 ms 680 KB Output is correct
3 Correct 5 ms 752 KB Output is correct
4 Execution timed out 1041 ms 39716 KB Time limit exceeded
5 Incorrect 610 ms 39716 KB Output isn't correct
6 Execution timed out 1038 ms 39716 KB Time limit exceeded
7 Execution timed out 1079 ms 39716 KB Time limit exceeded
8 Incorrect 931 ms 39716 KB Output isn't correct
9 Execution timed out 1087 ms 40544 KB Time limit exceeded
10 Incorrect 1000 ms 42980 KB Output isn't correct