# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
681056 | sudheerays123 | Vudu (COCI15_vudu) | C++17 | 339 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>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 1e6+5 , INF = 1e18 , MOD = 1e9+7;
vector<ll> seg(4*N);
void solve(){
ll n;
cin >> n;
vector<ll> a(n+5);
for(ll i = 1; i <= n; i++) cin >> a[i];
ll p;
cin >> p;
ll sum = 0;
set<ll> val;
val.insert(0);
for(ll i = 1; i <= n; i++){
sum += a[i];
val.insert(sum-p*i);
}
ll cnt = 0;
map<ll,ll> cc;
for(auto u : val){
cnt++;
cc[u] = cnt;
}
function<void(ll,ll,ll)> build = [&](ll node , ll left , ll right){
if(left == right){
seg[node] = 0;
return;
}
ll mid = (left+right)/2;
build(2*node,left,mid);
build(2*node+1,mid+1,right);
seg[node] = seg[2*node]+seg[2*node+1];
};
build(1,1,cnt);
function<void(ll,ll,ll,ll)> update = [&](ll node , ll left , ll right , ll pos){
if(left == right){
seg[node]++;
return;
}
ll mid = (left+right)/2;
if(pos <= mid) update(2*node,left,mid,pos);
else update(2*node+1,mid+1,right,pos);
seg[node] = seg[2*node]+seg[2*node+1];
};
update(1,1,cnt,cc[0]);
function<ll(ll,ll,ll,ll,ll)> query = [&](ll node , ll left , ll right , ll ql , ll qr){
if(left >= ql && right <= qr) return seg[node];
if(left > qr || right < ql) return 0ll;
ll mid = (left+right)/2;
ll l = query(2*node,left,mid,ql,qr);
ll r = query(2*node+1,mid+1,right,ql,qr);
return l+r;
};
ll ans = 0;
sum = 0;
for(ll i = 1; i <= n; i++){
sum += a[i];
ll s = sum-p*i;
ans += query(1,1,cnt,1,cc[s]);
update(1,1,cnt,cc[s]);
}
cout << ans;
}
int main(){
fast;
ll tc = 1;
// cin >> tc;
while(tc--) solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |