Submission #26671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26671	2017-07-04T15:28:04 Z	szawinis	Vudu (COCI15_vudu)	C++14	70 / 140	889 ms	65536 KB

vudu

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAX = (1e6)+1;

int n, p, a[MAX];
long long ans, sum[MAX];
ordered_set<pair<long long, int> > st;
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;
	st.insert(make_pair(0, 0));
	for(int i = 1; i <= n; i++) {
		sum[i] = sum[i-1] + a[i] - p;
		st.insert(make_pair(sum[i], i));
		ans += st.order_of_key(make_pair(sum[i], i));
	}
	cout << ans;
}

Subtask #1

70.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	14428 KB	Output is correct
2	Correct	3 ms	14296 KB	Output is correct
3	Correct	3 ms	14296 KB	Output is correct
4	Memory limit exceeded	889 ms	65536 KB	Memory limit exceeded
5	Correct	469 ms	48088 KB	Output is correct
6	Memory limit exceeded	663 ms	65536 KB	Memory limit exceeded
7	Memory limit exceeded	626 ms	65536 KB	Memory limit exceeded
8	Correct	579 ms	62080 KB	Output is correct
9	Memory limit exceeded	719 ms	65536 KB	Memory limit exceeded
10	Memory limit exceeded	613 ms	65536 KB	Memory limit exceeded