Submission #26673

#	Time	Username	Problem	Language	Result	Execution time	Memory
26673		szawinis	Vudu (COCI15_vudu)	C++14	56 / 140	729 ms	65536 KiB

vudu

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

int n, p, a[MAX], f[MAX];
long long ans, sum[MAX];
map<long long, int> pos;
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;
	vector<long long> tmp;
	tmp.push_back(0);
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + a[i] - p;
		tmp.push_back(sum[i]);
	}
	sort(tmp.begin(), tmp.end());
	tmp.resize(distance(tmp.begin(), unique(tmp.begin(), tmp.end())));
	for(int i = 0; i < tmp.size(); i++) pos[tmp[i]] = i+1;
	update(pos[0]);
	for(int i = 1; i <= n; i++) {
		ans += query(pos[sum[i]]);
		update(pos[sum[i]]);
	}
	cout << ans;
}

Compilation message (stderr)

vudu.cpp: In function 'int main()':
vudu.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < tmp.size(); i++) pos[tmp[i]] = i+1;
                   ^

• Subtask 1: 56 / 140