Submission #219226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219226	2020-04-04T16:09:39 Z	gabrc52	Vudu (COCI15_vudu)	C++14	56 / 140	578 ms	65540 KB

vudu

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_multiset;

const int MAXN=1e6;
int N;
int arr[MAXN];
int P;
indexed_multiset s;
ll ac[MAXN];
ll sum[MAXN];
ll dif[MAXN];
ll than;
ll ans;

void remove(ll val) {
	s.erase(s.find_by_order(s.order_of_key(val)));
}

int countLowerOrEqual(ll val) {
	return s.order_of_key(val+1);
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>N;
	for (int i=0; i<N; i++) {
		cin>>arr[i];
	}
	cin>>P;
	ac[0] = arr[0];
	for (int i=1; i<N; i++) {
		ac[i] = arr[i] + ac[i-1];
	}
	sum[0] = P;
	dif[0] = sum[0] - ac[0];
	for (int i=1; i<=N; i++) {
		sum[i] = sum[i-1] + P;
		dif[i] = sum[i] - ac[i];
	};
	for (int i=0; i<N; i++) {
		s.insert(dif[i]);
	}
	than = 0;
	ans += countLowerOrEqual(0);
	for (int i=1; i<N; i++) {
		remove(dif[i-1]);
		than += P - arr[i-1];
		ans += countLowerOrEqual(than);
	}
	cout<<ans<<'\n';
}

Subtask #1

56.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	1152 KB	Output is correct
2	Correct	8 ms	896 KB	Output is correct
3	Correct	8 ms	896 KB	Output is correct
4	Runtime error	436 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Correct	578 ms	49752 KB	Output is correct
6	Runtime error	392 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
7	Runtime error	384 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Runtime error	405 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
9	Runtime error	376 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
10	Runtime error	402 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)