oj.uz

Submission #94413

# Submission time Handle Problem Language Result Execution time Memory
94413 2019-01-18T09:21:59 Z theknife2001 Vudu (COCI15_vudu) C++11
0 / 140
 438 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*2];
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 104 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 124 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 48 ms 52244 KB Output isn't correct
4 Runtime error 170 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 199 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 161 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 438 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 211 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 175 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 146 ms 66560 KB Execution killed with signal 11 (could be triggered by violating memory limits)