# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
971883 | Sunbae | Vudu (COCI15_vudu) | C++17 | 32 ms | 5844 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>
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;
int m;
ll bit[N], qs[N], P;
vector<ll> cp;
int pos(ll x){return upper_bound(cp.begin(), cp.end(), x) - cp.begin();}
void upd(int i){for(; i<=m; i+=i&-i) ++bit[i];}
ll qry(int i){ll res = 0; for(; i; i-=i&-i) res += bit[i]; return res;}
signed main(){
int n; scanf("%d", &n);
for(int i = 1; i<=n; ++i){
scanf("%lld", qs+i);
qs[i] += qs[i-1];
}
scanf("%lld", &P);
for(ll i = 0; i<=n; ++i) cp.push_back(qs[i] - P*i);
sort(cp.begin(), cp.end()); cp.resize(unique(cp.begin(), cp.end()) - cp.begin()); m = cp.size();
upd(pos(0));
ll Ans = 0;
for(ll i = 1; i<=n; ++i){
Ans += qry(pos(qs[i] - P*i));
upd(pos(qs[i] - P*i));
}
printf("%lld", Ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |