oj.uz

Submission #201792

# Submission time Handle Problem Language Result Execution time Memory
201792 2020-02-12T02:19:38 Z mdn2002 Vudu (COCI15_vudu) C++14
42 / 140
 933 ms 65540 KB 
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,p,a[1000006],sum[1000006],tree[15000007];
vector<long long>pr;
map<long long,int>mp;
void up(int nod,int l,int r,int x)
{
    if(x<l||r<x)return;
    if(l==r)
    {
        tree[nod]++;
        return;
    }
    int mid=(l+r)/2;
    up(nod*2,l,mid,x);
    up(nod*2+1,mid+1,r,x);
    tree[nod]=tree[nod*2]+tree[nod*2+1];
}
long long qr(int nod,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return tree[nod];
    if(r<x||y<l)return 0;
    int mid=(l+r)/2;
    return qr(nod*2,l,mid,x,y)+qr(nod*2+1,mid+1,r,x,y);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("empty.in","r",stdin);
    //freopen("empty.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    cin>>p;
    for(int i=0;i<n;i++)
    {
        long long x=p-sum[i]+(p*i);
        long long y=-sum[i-1]+(p*i);
        pr.push_back(x);
        pr.push_back(y);
    }
    sort(pr.begin(),pr.end());
    int cnt=1;
    for(int i=0;i<pr.size();i++)
    {
        if(mp[pr[i]]==0)mp[pr[i]]=cnt++;
    }
    long long ans=0;
    for(int i=0;i<n;i++)
    {
        long long x=mp[p-sum[i]+(p*i)];
        long long y=mp[-sum[i-1]+(p*i)];
        up(1,0,n*2+55,y);
        ans+=qr(1,0,n*2+55,x,n*2+55);
    }
    cout<<ans;
}

Compilation message

vudu.cpp: In function 'int main()':
vudu.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<pr.size();i++)
                 ~^~~~~~~~~~

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1144 KB Output is correct
2 Correct 10 ms 1016 KB Output is correct
3 Correct 10 ms 1016 KB Output is correct
4 Runtime error 651 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 933 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 648 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 625 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 619 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 628 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 631 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)