oj.uz

Submission #310817

# Submission time Handle Problem Language Result Execution time Memory
310817 2020-10-08T05:06:55 Z Fischer Schools (IZhO13_school) C++14
30 / 100
 124 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 <= n) {
		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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 2 ms 1024 KB Output is correct
4 Incorrect 2 ms 1024 KB Output isn't correct
5 Incorrect 2 ms 1024 KB Output isn't correct
6 Incorrect 2 ms 1024 KB Output isn't correct
7 Incorrect 3 ms 1280 KB Output isn't correct
8 Correct 4 ms 1280 KB Output is correct
9 Incorrect 4 ms 1280 KB Output isn't correct
10 Incorrect 4 ms 1280 KB Output isn't correct
11 Incorrect 4 ms 1280 KB Output isn't correct
12 Incorrect 4 ms 1280 KB Output isn't correct
13 Incorrect 17 ms 2688 KB Output isn't correct
14 Incorrect 30 ms 4480 KB Output isn't correct
15 Incorrect 56 ms 8440 KB Output isn't correct
16 Correct 75 ms 7160 KB Output is correct
17 Incorrect 87 ms 9848 KB Output isn't correct
18 Incorrect 97 ms 11384 KB Output isn't correct
19 Incorrect 100 ms 11952 KB Output isn't correct
20 Correct 124 ms 13688 KB Output is correct