Submission #26674

#	Time	Username	Problem	Language	Result	Execution time	Memory
26674		szawinis	Vudu (COCI15_vudu)	C++14	140 / 140	289 ms	38512 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
const int MAX = (1e6)+1;

int n, p, f[MAX];
long long ans, a[MAX];
vector<pair<long long, int> > b;
void update(int i) { while(i <= n) f[i]++, i += i & -i; }
int query(int i) {
	int ret = 0;
	while(i > 0) ret += f[i], i -= i & -i;
	return ret;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cin >> p;
	ans = !p;
	b.emplace_back(0, 0);
	for(int i = 1; i <= n; i++) {
		a[i] += a[i-1] - p;
		b.emplace_back(a[i], i);
	}
	sort(b.begin(), b.end());
	for(auto p: b) {
		if(p.second) {
			ans += query(p.second);
			update(p.second);
		} else update(1);
	}
	cout << ans;
}

• Subtask 1: 140 / 140