#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000001
#define PI 3.14159265358979323846
#define ordered_set tree<pair<long long, int>, null_type,less<pair<long long, int> >, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin >> n;
int a[n];
ordered_set s;
//cout << n << '\n';
for(int i = 0; i < n; i++)
cin >> a[i];
long long p;
cin >> p;
long long sum=0, cu=0, ans=0;
for(int i = n-1; i >= 0; i--)
{
sum+=a[i];
s.insert(make_pair(sum-cu, i));
//cout << here[i] << ' ';
cu+=p;
}
//cout << '\n';
cu=0;
long long pr=0;
for(int i = n-1; i >= 0; i--)
{
if(s.lower_bound(make_pair(p+pr-cu, -1))!=s.end())
ans+=i+1-s.order_of_key(*s.lower_bound(make_pair(p+pr-cu, -1)));
//cout << s.order_of_key(*s.lower_bound(make_pair(p+pr-cu, -1))) << '\n';
pr+=a[i];
s.erase(make_pair(pr-cu, i));
cu+=p;
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
896 KB |
Output is correct |
| 2 |
Correct |
6 ms |
768 KB |
Output is correct |
| 3 |
Correct |
5 ms |
768 KB |
Output is correct |
| 4 |
Execution timed out |
1098 ms |
65536 KB |
Time limit exceeded |
| 5 |
Correct |
627 ms |
36856 KB |
Output is correct |
| 6 |
Correct |
970 ms |
57212 KB |
Output is correct |
| 7 |
Correct |
939 ms |
59640 KB |
Output is correct |
| 8 |
Correct |
897 ms |
51832 KB |
Output is correct |
| 9 |
Runtime error |
535 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Correct |
968 ms |
57976 KB |
Output is correct |
