제출 #951865

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
951865		MohamedAhmed04	Vudu (COCI15_vudu)	C++17	140 / 140	253 ms	27544 KiB

vudu

#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 / 140