oj.uz

Submission #219210

# Submission time Handle Problem Language Result Execution time Memory
219210 2020-04-04T15:14:47 Z DavidDamian Vudu (COCI15_vudu) C++11
0 / 140
 930 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll bit[1000006];
int n;
void update(int i,int v)
{
    while(i<=n){
        bit[i]+=v;
        i+=(i&(-i));
    }
}
int query(int i)
{
    int ans=0;
    while(i>0){
        ans+=bit[i];
        i-=(i&(-i));
    }
    return ans;
}
int getSum(int a,int b)
{
    return query(b)-query(a-1);
}
typedef pair<ll,int> pii;
unordered_map<ll,int> remap;
ll k;
ll A[1000006];
ll S[1000006];
ll S_K[1000006]; //S[i]-k*i
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    cin>>k;
    remap[0]=1;
    for(ll i=1;i<=n;i++){
        S[i]=S[i-1]+A[i];
        S_K[i]=S[i]-k*i;
        remap[ S_K[i] ]=1;
    }
    int id=1;
    for(pii p: remap){
        remap[p.first]=id++;
    }
    ll total=0;
    for(int i=0;i<=n;i++){
        S_K[i]=remap[ S_K[i] ];
        if(i>0) total+=getSum(1,S_K[i]);
        update(S_K[i],1);
    }
    cout<<total<<'\n';
    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1024 KB Output isn't correct
2 Incorrect 6 ms 768 KB Output isn't correct
3 Incorrect 7 ms 896 KB Output isn't correct
4 Runtime error 483 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Incorrect 565 ms 47084 KB Output isn't correct
6 Incorrect 906 ms 65536 KB Output isn't correct
7 Incorrect 930 ms 65536 KB Output isn't correct
8 Incorrect 802 ms 63344 KB Output isn't correct
9 Runtime error 487 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Incorrect 901 ms 65536 KB Output isn't correct