Submission #94412

#	Time	Username	Problem	Language	Result	Execution time	Memory
94412		theknife2001	Vudu (COCI15_vudu)	C++11	0 / 140	63 ms	66560 KiB

vudu

#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2

using namespace std;
const int N=1e6+55;
vector < ll > tree[N*4];
ll sum[N];
ll a[N];

void merg(vector < ll > &vec , vector < ll > &a , vector < ll > &b)
{
    unsigned int i=0,j=0;
    for(int k=0;i<a.size()||j<b.size();k++)
    {
        if(j==b.size()||a[i]<=b[j])
        {
            vec.push_back(a[i]);
            i++;
        }
        else
        {
            vec.push_back(b[j]);
            j++;
        }
    }
}

void build(int node , int l , int r)
{
    if(l==r)
    {
        tree[node].push_back(sum[l]);
        return ;
    }
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    merg(tree[node],tree[node*2],tree[node*2+1]);
}



int query(int node, int l , int r , int x , int y , ll val)
{
    if(r<x||l>y)
        return 0;
    if(x<=l&&r<=y)
        return (tree[node].end()-lower_bound(tree[node].begin(),tree[node].end(),val));
    return query(node*2,l,mid,x,y,val)+query(node*2+1,mid+1,r,x,y,val);
}


int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int P;
    cin>>P;
    for(int i=0;i<n;i++)
    {
        sum[i]=a[i]-P;
        if(i)
            sum[i]+=sum[i-1];
    }
    build(1,0,n-1);
    ll ans=0;
    ll x=0;
    for(int i=0;i<n;i++)
    {
        ans+=query(1,0,n-1,i,n-1,x);
        x+=a[i]-P;
    }
    cout<<ans<<endl;
    return 0;
}

• Subtask 1: 0 / 140