oj.uz

Submission #94412

# Submission time Handle Problem Language Result Execution time Memory
94412 2019-01-18T09:21:25 Z theknife2001 Vudu (COCI15_vudu) C++11
0 / 140
 63 ms 66560 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 61 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 60 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 63 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 56 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 61 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 61 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 60 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 61 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 62 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)