#include<bits/stdc++.h>
// 6 47
typedef long long ll;
#define NMAX 1000005
#define SMAX 2300000
using namespace std;
int tree[SMAX];
void upd(int i, int s, int e, int indx){
if(s == e){
tree[i] = 1;
return;
}
int m = (s + e)>>1;
if(indx <= m) upd(i*2, s, m, indx);
else upd(i*2+1, m+1, e, indx);
tree[i] = tree[i*2] + tree[i*2+1];
}
ll query(int i, int s, int e, int l, int r){
if(s >= l && e <= r) return tree[i];
if(s > r || e < l) return 0;
int m = (s + e)>>1;
return query(i*2, s, m, l, r) + query(i*2+1, m+1, e, l, r);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int n; cin>>n;
ll a[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}
ll p; cin>>p;
vector<pair<ll, int> > vi;
ll zero = 0;
for(int i = n-1; i >= 0; i--){
a[i] -= p;
zero -= a[i];
ll cur = zero + a[i];
//cout<<i<<" PUSH: "<<cur<<endl;
vi.push_back({cur, i});
}
sort(vi.begin(), vi.end());
vector<int> indx(n);
for(int i = 0; i < n; i++){
indx[vi[i].second] = i;
}
ll ans = 0; zero = 0;
for(int i = n-1; i >= 0; i--){
upd(1, 0, n-1, indx[i]);
zero -= a[i];
pair<ll, int> temp = {zero, 0};
int index = lower_bound(vi.begin(), vi.end(), temp) - vi.begin();
ans += query(1, 0, n-1, index, n-1);
}
cout<<ans<<endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
760 KB |
Output is correct |
2 |
Correct |
5 ms |
760 KB |
Output is correct |
3 |
Correct |
6 ms |
772 KB |
Output is correct |
4 |
Execution timed out |
1065 ms |
35200 KB |
Time limit exceeded |
5 |
Correct |
554 ms |
35200 KB |
Output is correct |
6 |
Correct |
948 ms |
35200 KB |
Output is correct |
7 |
Correct |
846 ms |
35200 KB |
Output is correct |
8 |
Correct |
834 ms |
35200 KB |
Output is correct |
9 |
Execution timed out |
1063 ms |
36232 KB |
Time limit exceeded |
10 |
Correct |
899 ms |
36232 KB |
Output is correct |