# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
49423 | rzbt | Vudu (COCI15_vudu) | C++14 | 1095 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 1000005
typedef long long ll;
using namespace std;
ll n,p,res;
ll niz[MAXN];
ll bit[MAXN];
void update(ll p,ll x){
for(;p<MAXN;p+=(p&(-p)))
bit[p]+=x;
}
ll dobij(ll p){
ll z=0;
for(;p>0;p-=(p&(-p)))
z+=bit[p];
return z;
}
set<ll> s;
map<ll,ll> m;
int main()
{
scanf("%lld", &n);
for(ll i=1;i<=n;i++)
scanf("%lld",niz+i);
ll tzbir=0;
scanf("%lld",&p);
for(ll i=1;i<=n;i++){
tzbir+=niz[i]-p;
s.insert(tzbir);
}
ll tbr=0;
for(auto x:s){
tbr++;
m[x]=tbr;
}
tzbir=0;
for(ll i=1;i<=n;i++){
tzbir+=niz[i]-p;
if(tzbir>=0)res++;
ll t=m[tzbir];
res+=dobij(t);
update(t,1);
}
printf("%lld",res);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |