# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
946667 | NourWael | Vudu (COCI15_vudu) | C++17 | 494 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/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
int const mxN = 1e6;
int a[mxN + 1];
int seg[4*mxN];
map<int,int> val;
int get ( int node, int l, int r, int ind) {
if(ind<l) return 0;
if(r-1<=ind) return seg[node];
int m = (l+r) / 2;
return get(node*2+1, l, m, ind) + get(node*2+2, m, r, ind);
}
void update ( int node, int l, int r, int ind) {
if(ind<l || ind>=r) return;
if(l==r-1 && l==ind) {
seg[node] += 1;
return;
}
int m = (l+r) / 2;
update(node*2+1, l, m, ind), update(node*2+2, m, r, ind);
seg[node] = seg[node*2+1] + seg[node*2+2];
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int n,p, ans = 0, ind = 0; cin>>n;
for(int i=0; i<n; i++) cin>>a[i];
cin>>p;
vector<int> st;
st.push_back(p);
for(int i=0; i<n; i++) {
a[i] += (i? a[i-1]:0);
int x = a[i] - p*i;
st.push_back(x);
}
sort(st.begin(),st.end());
val[st[0]] = 0;
for(int i=1; i<st.size(); i++) {
if(st[i]==st[i-1]) continue;
ind++;
val[st[i]] = ind;
}
int pw = (1<<(__lg(ind-1)+1));
update(0,0,pw, val[p]);
for(int i=0; i<n; i++) {
int x = a[i] - p*i;
x = val[x];
ans += get(0,0,pw, x);
update(0,0,pw,x);
}
cout<<ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |