Submission #219230

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219230	2020-04-04T16:11:46 Z	gabrc52	Vudu (COCI15_vudu)	C++14	42 / 140	467 ms	35832 KB

vudu

#include <iostream>
#include <cassert>
#include <algorithm>

using namespace std;
typedef long long ll;

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

void inc(int i) {
	for (; i < N; i |= i+1) ++ft[i];
}

ll get(int i) {
	ll r = 0;
	for (; i >= 0; i = (i&(i+1)) - 1) r += ft[i];
	return r;
}

void remove(int val) {
	int lb = lower_bound(sorted,sorted+N,val) - sorted;
	inc(lb);
}

int countLowerOrEqual(int val) {
	int ub = upper_bound(sorted,sorted+N,val) - sorted;
	return ub - get(ub-1);
	return 0;
}

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;
	sorted[0] = dif[0] = sum[0] - ac[0];
	for (int i=1; i<=N; i++) {
		sum[i] = sum[i-1] + P;
		sorted[i] = dif[i] = sum[i] - ac[i];
	}
	sort(sorted, sorted+N);
	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

42.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	768 KB	Output is correct
2	Correct	6 ms	640 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Incorrect	408 ms	34424 KB	Output isn't correct
5	Incorrect	274 ms	19960 KB	Output isn't correct
6	Incorrect	396 ms	30696 KB	Output isn't correct
7	Incorrect	368 ms	31864 KB	Output isn't correct
8	Incorrect	281 ms	27640 KB	Output isn't correct
9	Incorrect	467 ms	35832 KB	Output isn't correct
10	Incorrect	414 ms	31096 KB	Output isn't correct