Submission #310818

#	Time	Username	Problem	Language	Result	Execution time	Memory
310818		Fischer	Schools (IZhO13_school)	C++14	100 / 100	120 ms	13688 KiB

school

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

const int maxN = 1<<19;
using ll = long long;
struct Pair {
		int a, b, id;
} arr[maxN], temp_arr[maxN];
int n, m, s;
int invS[maxN], pS[maxN];
ll ds[maxN];
pair<int, ll> ft[maxN];

void update(int x, int u, int v) {
	while (x < maxN) {
		ft[x].first += u;
		ft[x].second += v;
		x += x&-x;
	}
}

ll query(int need) {
	ll ans = 0, cur = 0;
	for (int pos = 18; pos >= 0; --pos) {
		if (need >= ft[cur + (1<<pos)].first) {
			ans += ft[cur + (1<<pos)].second;
			need -= ft[cur + (1<<pos)].first;
			cur += (1<<pos);
		}
	}
	return ans;
}

const int maxAB = maxN / 3;
int cnt[maxAB];

int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d", &arr[i].a, &arr[i].b);
		cnt[arr[i].b] += 1;
	}
	for (int i = 1; i <= maxAB; ++i) {
		cnt[i] += cnt[i-1];
	}
	ll add = 0;
	for (int i = 0, j = 0; i < n; ++i) {
		int cur_pos = cnt[arr[i].b]--;
		arr[i].id = n - cur_pos;
		if (arr[i].id < s) {
			ds[j++] = arr[i].a - arr[i].b;
			add += arr[i].b;
		}
	}
	sort(ds, ds+s, greater<>());
	for (int i = 0; i <= maxAB; ++i) cnt[i] = 0;
	for (int i = 0; i < n; ++i) {
		cnt[arr[i].a] += 1;
		temp_arr[i] = arr[i];
	}
	for (int i = 1; i <= maxAB; ++i) {
		cnt[i] += cnt[i-1];
	}
	for (int i = 0; i < n; ++i) {
		int cur_pos = cnt[temp_arr[i].a]--;
		arr[n - cur_pos] = temp_arr[i];
	}
	for (int i = 0, j = 0; i < n; ++i) {
		if (arr[i].id < s) continue;
		invS[arr[i].id] = ++j;
		pS[arr[i].id] = i;
		update(invS[arr[i].id], 1, arr[i].a);
	}
	priority_queue<int, vector<int>, greater<>> kSet;
	int posS = 0;
	ll ans = -1e18;
	for (int i = 0; i <= m; ++i) {
		ans = max(ans, add + query(m - i));
		if (i == m) break;
		auto new_element = arr[pS[s+i]];
		update(invS[s+i], -1, -new_element.a);
		add += new_element.a;
		int delta = new_element.b - new_element.a;
		while (!kSet.empty() && delta > kSet.top()) {
			if (posS >= s || ds[posS] + kSet.top() < 0) {
				add -= kSet.top();
				kSet.pop();
				posS -= 1;
				add -= ds[posS];
			} else break;
		}
		if (posS >= s) {
			if (!kSet.empty() && kSet.top() < delta) {
				add += delta - kSet.top();
				kSet.pop();
				kSet.push(delta);
			}
		} else {
			if (delta + ds[posS] > 0) {
				add += delta + ds[posS++];
				kSet.push(delta);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

school.cpp: In function 'int main()':
school.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  scanf("%d%d%d", &n, &m, &s);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |   scanf("%d%d", &arr[i].a, &arr[i].b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:44:10: warning: iteration 174761 invokes undefined behavior [-Waggressive-loop-optimizations]
   44 |   cnt[i] += cnt[i-1];
      |   ~~~~~~~^~~~~~~~~~~
school.cpp:43:20: note: within this loop
   43 |  for (int i = 1; i <= maxAB; ++i) {
      |                  ~~^~~~~~~~
school.cpp:56:42: warning: iteration 174762 invokes undefined behavior [-Waggressive-loop-optimizations]
   56 |  for (int i = 0; i <= maxAB; ++i) cnt[i] = 0;
      |                                   ~~~~~~~^~~
school.cpp:56:20: note: within this loop
   56 |  for (int i = 0; i <= maxAB; ++i) cnt[i] = 0;
      |                  ~~^~~~~~~~
school.cpp:62:10: warning: iteration 174761 invokes undefined behavior [-Waggressive-loop-optimizations]
   62 |   cnt[i] += cnt[i-1];
      |   ~~~~~~~^~~~~~~~~~~
school.cpp:61:20: note: within this loop
   61 |  for (int i = 1; i <= maxAB; ++i) {
      |                  ~~^~~~~~~~

• Subtask 1: 100 / 100