Submission #1172813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172813		nuutsnoynton	Vudu (COCI15_vudu)	C++20	42 / 140	1089 ms	131072 KiB

vudu

#include<bits/stdc++.h>

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

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() {
	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];
	}
	map < ll, ll > A, To;
	for (i =0; i <= n; i ++) {
		a[i] = a[i] - m * i;
		A[a[i]] ++;
	}
	
	cnt = 1;
	
	for ( auto R : A) {
		To[R.first] = cnt;
		cnt ++;
	}
	
	for (i = 0; i <= n; i ++) {
		a[i] = To[a[i]];
	}
	
	ans = 0;
	for (i = 0; i <= n; i ++) {
		s = Find(1, 1, 1e6, 1, a[i]);
		ans += s;
		Update(1, 1, 1e6, a[i]);
	}
	cout << ans << endl;
	
	
	
	
}

• Subtask 1: 42 / 140