oj.uz

Submission #951865

# Submission time Handle Problem Language Result Execution time Memory
951865 2024-03-22T21:00:15 Z MohamedAhmed04 Vudu (COCI15_vudu) C++17
140 / 140
 253 ms 27544 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e6 + 10 ;

int n , p ;
int arr[MAX] ;

int bit[MAX] ;

void add(int i, int x)
{
    for(; i <= n+1 ; i += (i & (-i)))
        bit[i] += x ;
}

int get(int i)
{
    int sum = 0 ;
    for(; i > 0 ; i -= (i & (-i)))
        sum += bit[i] ;
    return sum ;
}

int sumid[MAX] ;

void compress()
{
    vector<long long>v = {0} ;
    long long sum = 0 ;
    for(int i = 1 ; i <= n ; ++i)
        sum += arr[i], v.push_back(sum) ;
    sort(v.begin() , v.end()) ;
    v.erase(unique(v.begin() , v.end()) , v.end()) ;
    sum = 0 ;
    for(int i = 0 ; i <= n ; ++i)
    {
        sum += arr[i] ;
        sumid[i] = lower_bound(v.begin() , v.end() , sum) - v.begin() ;
        sumid[i]++ ;
    }
}

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(0) ;
    cin>>n ;
    for(int i = 1 ; i <= n ; ++i)
        cin>>arr[i] ;
    cin>>p ;
    for(int i = 1 ; i <= n ; ++i)
        arr[i] -= p ;
    compress() ;
    add(sumid[0], 1) ;
    long long ans = 0 ;
    for(int i = 1 ; i <= n ; ++i)
        ans += get(sumid[i]) , add(sumid[i], 1) ;
    return cout<<ans<<"\n" , 0 ;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 251 ms 27508 KB Output is correct
5 Correct 133 ms 17884 KB Output is correct
6 Correct 218 ms 24332 KB Output is correct
7 Correct 222 ms 24940 KB Output is correct
8 Correct 189 ms 22664 KB Output is correct
9 Correct 253 ms 27544 KB Output is correct
10 Correct 215 ms 23220 KB Output is correct