Submission #443152

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
443152	2021-07-09T20:51:51 Z	aryan12	Vudu (COCI15_vudu)	C++17	140 / 140	501 ms	39556 KB

vudu

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e6 + 5;
int n, avg;
vector<int> a;
int BIT[N];

bool cmp(pair<int, int> a, pair<int, int> b) {
	return ((avg * a.second - a.first) > (avg * b.second - b.first));
}

void Update(int pos, int val) {
	for(int i = pos; i < N; i += (i & (-i))) {
		BIT[i] += val;
	}
}

int Query(int pos) {
	int ans = 0;
	for(int i = pos; i > 0; i -= (i & (-i))) {
		ans += BIT[i];
	}
	return ans;
}

void Solve() {
	cin >> n;
	a.resize(n + 1);
	for(int i = 0; i < N; i++) {
		BIT[i] = 0;
	}
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	cin >> avg;
	vector<pair<int, int> > min_suf;
	min_suf.push_back(make_pair(-1, -1));
	int sum = 0;
	for(int i = n; i > 0; i--) {
		sum += a[i];
		min_suf.push_back(make_pair(sum, n - i + 1));
	}
	min_suf.push_back(make_pair(0, 0));
	int total = n * avg - sum;
	sort(min_suf.begin() + 1, min_suf.end(), cmp);
	sum = 0;
	//cout << "total = " << total << "\n";
	int res = 0;

	int pos[n + 1];
	for(int i = 1; i < min_suf.size(); i++) {
		if(min_suf[i].second != 0) {
			pos[n + 1 - min_suf[i].second] = i;
		}
	} 

	for(int i = 1; i <= n; i++) {
		Update(pos[i], 1);
		int l = 1, r = min_suf.size() - 1;
		int mid, ans = 0;
		while(l <= r) {
			mid = (l + r) >> 1;
			auto [s, len] = min_suf[mid];
			int val = avg * len - s; //+ve - bad val gone
			int prevval = (i - 1) * avg - sum;
			if(prevval + val >= total) {
				l = mid + 1;
				ans = mid;
			}
			else {
				r = mid - 1;
			}
		}
		//cout << "Index = " << i << "\n";
		//cout << "answer = " << ans << "\n";
		//cout << "Query(answer) = " << Query(ans) << "\n";
		//cout << "Thus, final answer = " << ans - Query(ans) << "\n";
		res += ans;
		res -= Query(ans);
		sum += a[i];
	}
	cout << res << "\n";
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message

vudu.cpp: In function 'void Solve()':
vudu.cpp:55:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 1; i < min_suf.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	8524 KB	Output is correct
2	Correct	6 ms	8396 KB	Output is correct
3	Correct	6 ms	8416 KB	Output is correct
4	Correct	501 ms	38572 KB	Output is correct
5	Correct	264 ms	28980 KB	Output is correct
6	Correct	411 ms	35144 KB	Output is correct
7	Correct	418 ms	36048 KB	Output is correct
8	Correct	363 ms	32320 KB	Output is correct
9	Correct	459 ms	39556 KB	Output is correct
10	Correct	406 ms	35476 KB	Output is correct