Submission #26674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26674	2017-07-04T15:51:14 Z	szawinis	Vudu (COCI15_vudu)	C++14	140 / 140	289 ms	38512 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	14056 KB	Output is correct
2	Correct	0 ms	14056 KB	Output is correct
3	Correct	0 ms	14056 KB	Output is correct
4	Correct	276 ms	38512 KB	Output is correct
5	Correct	173 ms	38512 KB	Output is correct
6	Correct	239 ms	38512 KB	Output is correct
7	Correct	209 ms	38512 KB	Output is correct
8	Correct	209 ms	38512 KB	Output is correct
9	Correct	289 ms	38512 KB	Output is correct
10	Correct	226 ms	38512 KB	Output is correct