oj.uz

Submission #94483

# Submission time Handle Problem Language Result Execution time Memory
94483 2019-01-19T10:03:30 Z theknife2001 Vudu (COCI15_vudu) C++11
0 / 140
 205 ms 41516 KB 
#include <bits/stdc++.h>
#define ll long long
#define mid (l+r)/2

using namespace std;
map < ll , int > mp;
const int N=1e6+55;
int tree[N];
ll sum[N];
ll a[N];
int n;

int query(int x)
{
    if(x<=0)
        return 0;
    return query(x-(x&(-x)))+tree[x];
}

void update(int x)
{
    if(x>n)
        return ;
    tree[x]++;
    update(x+(x&(-x)));
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int p;
    cin>>p;
    for(int i=n-1;i>=0;i--)
    {
        sum[i]=a[i]-p;
        if(i!=n-1)
            sum[i]+=sum[i+1];
        a[i]=sum[i];
    }
    sort(a,a+n);
    int cnt=1;
    assert(0);
    for(int i=0;i<n;i++)
    {
        if(mp[a[i]]==0)
            mp[a[i]]=cnt++;
    }
    ll ans=0;
    for(int i=n-1;i>=0;i--)
    {
        if(sum[i]>=0)
            ans++;
        ans+=query(mp[sum[i]]);
        update(mp[sum[i]]);
    }
    cout<<ans<<endl;
    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 4 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 205 ms 39672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 112 ms 17784 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 175 ms 32236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 181 ms 33168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 155 ms 24824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 198 ms 41516 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 172 ms 32508 KB Execution killed with signal 11 (could be triggered by violating memory limits)