| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 256554 | 2020-08-02T20:42:24 Z | ElyesChaabouni | Vudu (COCI15_vudu) | C++14 | 0 ms | 0 KB |
#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);
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
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];
here[i]=sum-cu;
s.insert(make_pair(here[i], 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';
}