# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
875546 |
2023-11-20T03:23:30 Z |
12345678 |
Vudu (COCI15_vudu) |
C++17 |
|
310 ms |
20000 KB |
#include <bits/stdc++.h>
using namespace std;
const int nx=1e6+5;
long long n, p, qs[nx], res;
vector<long long> v;
struct fenwick
{
int d[nx];
void add(int idx)
{
for (int i=idx; i<=n; i+=(i&-i)) d[i]++;
}
int query(int idx)
{
int res=0;
for (int i=idx; i>0; i-=(i&-i)) res+=d[i];
return res;
}
} f;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n;
for (int i=1; i<=n; i++) cin>>qs[i], qs[i]+=qs[i-1];
cin>>p;
for (int i=0; i<n; i++) v.push_back(qs[i]-i*p);
v.push_back(LLONG_MAX);
sort(v.begin(), v.end());
//for (auto x:v) cout<<x<<'\n';
for (int i=1; i<=n; i++)
{
f.add(upper_bound(v.begin(), v.end(), qs[i-1]-(i-1)*p)-v.begin());
res+=f.query(upper_bound(v.begin(), v.end(), qs[i]-(i)*p)-v.begin());
}
cout<<res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2648 KB |
Output is correct |
2 |
Correct |
2 ms |
2652 KB |
Output is correct |
3 |
Correct |
2 ms |
2652 KB |
Output is correct |
4 |
Correct |
309 ms |
19496 KB |
Output is correct |
5 |
Correct |
165 ms |
15048 KB |
Output is correct |
6 |
Correct |
267 ms |
19388 KB |
Output is correct |
7 |
Correct |
268 ms |
19516 KB |
Output is correct |
8 |
Correct |
238 ms |
19000 KB |
Output is correct |
9 |
Correct |
310 ms |
20000 KB |
Output is correct |
10 |
Correct |
260 ms |
17848 KB |
Output is correct |