oj.uz

Submission #310816

# Submission time Handle Problem Language Result Execution time Memory
310816 2020-10-08T04:56:53 Z Fischer Schools (IZhO13_school) C++14
75 / 100
 2000 ms 13432 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 3e5 + 10;
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));
		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 100002 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 100003 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 100002 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
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 768 KB Time limit exceeded
2 Execution timed out 2044 ms 768 KB Time limit exceeded
3 Execution timed out 2065 ms 768 KB Time limit exceeded
4 Correct 1 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 3 ms 1024 KB Output is correct
8 Execution timed out 2029 ms 1024 KB Time limit exceeded
9 Correct 3 ms 1024 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 3 ms 1024 KB Output is correct
12 Correct 4 ms 896 KB Output is correct
13 Correct 18 ms 2432 KB Output is correct
14 Correct 33 ms 4096 KB Output is correct
15 Correct 58 ms 8160 KB Output is correct
16 Execution timed out 2073 ms 6808 KB Time limit exceeded
17 Correct 92 ms 9592 KB Output is correct
18 Correct 103 ms 11092 KB Output is correct
19 Correct 109 ms 11640 KB Output is correct
20 Correct 126 ms 13432 KB Output is correct