Submission #26673

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26673	2017-07-04T15:38:04 Z	szawinis	Vudu (COCI15_vudu)	C++14	56 / 140	729 ms	65536 KB

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

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.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	18236 KB	Output is correct
2	Correct	3 ms	18236 KB	Output is correct
3	Correct	3 ms	18104 KB	Output is correct
4	Memory limit exceeded	409 ms	65536 KB	Memory limit exceeded
5	Correct	729 ms	60096 KB	Output is correct
6	Memory limit exceeded	413 ms	65536 KB	Memory limit exceeded
7	Memory limit exceeded	409 ms	65536 KB	Memory limit exceeded
8	Memory limit exceeded	336 ms	65536 KB	Memory limit exceeded
9	Memory limit exceeded	449 ms	65536 KB	Memory limit exceeded
10	Memory limit exceeded	366 ms	65536 KB	Memory limit exceeded