Submission #1172817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172817		nuutsnoynton	Vudu (COCI15_vudu)	C++20	0 / 140	156 ms	24736 KiB

vudu

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const ll N = 1e6 + 4;

ll T[4 * N];

ll Find(ll p, ll lo, ll hi, ll l, ll r) {
	if ( lo > r || l > hi) return 0;
	if ( l <= lo && hi <= r) {
		return T[p];
	}
	ll mid = (lo + hi)/2;
	return Find(2 * p, lo, mid, l, r) + Find(2 * p + 1, mid + 1, hi, l, r);
}

void Update(ll p, ll lo, ll hi, ll x) {
	if ( lo == hi) {
		T[p] ++;
		return ;
	}
	ll mid = (lo + hi)/2;
	if ( x <= mid) Update(2 * p, lo, mid, x);
	else Update(2 * p + 1, mid + 1, hi, x);
	T[p] = T[2 * p] + T[2 * p + 1];
	return ;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	ll n, m, r,s, cnt, x, y, can, i, j, ans, t;

	cin >> n;	
	
	ll a[n + 2];
	
	for (i = 1; i <= n; i++) {
		cin >> a[i];
	}	
	
	cin >> m;
	
	a[0] = 0;
	for (i= 1; i <= n; i ++) {
		a[i] = a[i - 1] + a[i];
	}
	vector < pair < ll, ll > > v;	
	for (i =0; i <= n; i ++) {
		a[i] = a[i] - m * i;
		v.push_back(make_pair(a[i], i));
	}
	
	
	ans = 0;
	for (i = 0; i <= n; i ++) {
		s = Find(1, 0, n, 0, v[i].first);
		ans += s;
		Update(1, 0, n, v[i].first);
	}
	cout << ans << endl;
	
	
	
	
}

• Subtask 1: 0 / 140