Submission #26671

#	Time	Username	Problem	Language	Result	Execution time	Memory
26671		szawinis	Vudu (COCI15_vudu)	C++14	70 / 140	889 ms	65536 KiB

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 / 140