oj.uz

Submission #310818

# Submission time Handle Problem Language Result Execution time Memory
310818 2020-10-08T05:10:02 Z Fischer Schools (IZhO13_school) C++14
100 / 100
 120 ms 13688 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1152 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 2 ms 1152 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 2 ms 1152 KB Output is correct
6 Correct 2 ms 1152 KB Output is correct
7 Correct 4 ms 1280 KB Output is correct
8 Correct 4 ms 1280 KB Output is correct
9 Correct 4 ms 1280 KB Output is correct
10 Correct 4 ms 1280 KB Output is correct
11 Correct 4 ms 1280 KB Output is correct
12 Correct 4 ms 1280 KB Output is correct
13 Correct 18 ms 2688 KB Output is correct
14 Correct 31 ms 4472 KB Output is correct
15 Correct 57 ms 8440 KB Output is correct
16 Correct 73 ms 7104 KB Output is correct
17 Correct 92 ms 9848 KB Output is correct
18 Correct 101 ms 11388 KB Output is correct
19 Correct 114 ms 11952 KB Output is correct
20 Correct 120 ms 13688 KB Output is correct