Submission #1265926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265926		canhnam357	Vudu (COCI15_vudu)	C++20	140 / 140	236 ms	23876 KiB

vudu

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
#define int long long
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
struct fenwick
{
	int n;
	vector<int> bit;
	fenwick() {}
	fenwick(int n)
	{
		this->n = n + 5;
		bit.resize(n + 5);
	}
	void add(int pos, int val)
	{
		while (pos < n)
		{
			bit[pos] += val;
			pos += pos & -pos;
		}
	}
	int get(int pos)
	{
		int ans = 0;
		while (pos)
		{
			ans += bit[pos];
			pos -= pos & -pos;
		}
		return ans;
	}
	int get(int l, int r)
	{
		return get(r) - get(l - 1);
	}
};
void solve()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) cin >> i;
	int p;
	cin >> p;
	for (int& i : a) i -= p;
	for (int i = 1; i < n; i++) a[i] += a[i - 1];
	auto cc = a;
	cc.push_back(0);
	sort(all(cc));
	cc.erase(unique(all(cc)), cc.end());
	auto get = [&](int val)
	{
		return upper_bound(all(cc), val) - cc.begin();
	};
	fenwick tree(cc.size());
	tree.add(get(0), 1);
	int ans = 0;
	for (int i : a)
	{
		int pos = get(i);
		ans += tree.get(pos);
		tree.add(pos, 1);
	}
	cout << ans;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while (t--) solve();
	return 0;
}

• Subtask 1: 140 / 140