oj.uz

Submission #484897

# Submission time Handle Problem Language Result Execution time Memory
484897 2021-11-05T17:37:17 Z imachug Teams (IOI15_teams) C++17
100 / 100
 1910 ms 129508 KB 
#include "teams.h"


#include <bits/stdc++.h>

using namespace std;


class MergeSortTree {
public:
	int n;
	vector<vector<int>> a;

	void build(const vector<int>& data) {
		n = data.size();
		a.resize(4 * n);
		build(1, 0, n, data);
	}
	void build(int v, int vl, int vr, const vector<int>& data) {
		if(vr - vl == 1) {
			a[v].push_back(data[vl]);
		} else {
			int vm = (vl + vr) / 2;
			build(v * 2, vl, vm, data);
			build(v * 2 + 1, vm, vr, data);
			a[v].resize(vr - vl);
			merge(a[v * 2].begin(), a[v * 2].end(), a[v * 2 + 1].begin(), a[v * 2 + 1].end(), a[v].begin());
		}
	}

	int cnt_in_range(int v, int vl, int vr, int l, int r, int low, int high) {
		if(vl == l && vr == r) {
			return lower_bound(a[v].begin(), a[v].end(), high) - lower_bound(a[v].begin(), a[v].end(), low);
		}
		int vm = (vl + vr) / 2;
		if(r <= vm) {
			return cnt_in_range(v * 2, vl, vm, l, r, low, high);
		} else if(l >= vm) {
			return cnt_in_range(v * 2 + 1, vm, vr, l, r, low, high);
		} else {
			return cnt_in_range(v * 2, vl, vm, l, vm, low, high) + cnt_in_range(v * 2 + 1, vm, vr, vm, r, low, high);
		}
	}
	int cnt_in_range(int l, int r, int low, int high) {
		if(l == r || low >= high) {
			return 0;
		}
		return cnt_in_range(1, 0, n, l, r, low, high);
	}

	int first_cnt_in_range(int v, int vl, int vr, int l, int r, int low, int high, int cnt) {
		while(vr - vl > 1) {
			int vm = (vl + vr) / 2;
			if(r <= vm) {
				v = v * 2;
				vr = vm;
			} else if(l >= vm) {
				v = v * 2 + 1;
				vl = vm;
			} else {
				int cnt_left = cnt_in_range(v * 2, vl, vm, l, vm, low, high);
				if(cnt_left >= cnt) {
					v = v * 2;
					vr = vm;
					r = vm;
				} else {
					cnt -= cnt_left;
					v = v * 2 + 1;
					vl = vm;
					l = vm;
				}
			}
		}

		if(cnt == 0) {
			return l;
		} else {
			assert(cnt == 1 && a[v][0] >= low && a[v][0] < high);
			return r;
		}
	}

	int first_cnt_in_range(int l, int r, int low, int high, int cnt) {
		if(cnt == 0) {
			return l;
		}
		return first_cnt_in_range(1, 0, n, l, r, low, high, cnt);
	}
};


vector<pair<int, int>> students;
MergeSortTree students_first_mst;


void init(int n, int a[], int b[]) {
	for(int i = 0; i < n; i++) {
		students.emplace_back(a[i], b[i]);
	}

	sort(students.begin(), students.end(), [](pair<int, int> p1, pair<int, int> p2) {
		return p1.second < p2.second;
	});

	vector<int> students_first(n);
	for(int i = 0; i < n; i++) {
		students_first[i] = students[i].first;
	}
	students_first_mst.build(students_first);
}


int can(int m, int k[]) {
	sort(k, k + m);

	long long total = 0;
	for(int i = 0; i < m; i++) {
		total += k[i];
	}
	if(total > students.size()) {
		return 0;
	}

	multiset<pair<int, int>> disabled_intervals;
	disabled_intervals.emplace(students.size(), 0);

	for(int i = 0; i < m; i++) {
		int l = lower_bound(students.begin(), students.end(), make_pair(0, k[i]), [](pair<int, int> p1, pair<int, int> p2) {
			return p1.second < p2.second;
		}) - students.begin();
		if(l == students.size()) {
			return 0;
		}

		while(disabled_intervals.begin()->first <= l) {
			disabled_intervals.erase(disabled_intervals.begin());
		}


		int cnt = 0;

		int r = l;

		while(!disabled_intervals.empty()) {
			auto [r1, x] = *disabled_intervals.begin();

			// search in range r..r1
			int cnt_in_range = students_first_mst.cnt_in_range(r, r1, x + 1, k[i] + 1);
			if(cnt + cnt_in_range < k[i]) {
				// Have to take the whole range
				cnt += cnt_in_range;
				r = r1;
				disabled_intervals.erase(disabled_intervals.begin());
			} else {
				// This range is certainly enough to finish the project
				r = students_first_mst.first_cnt_in_range(r, r1, x + 1, k[i] + 1, k[i] - cnt);
				cnt = k[i];
				if(r == r1) {
					disabled_intervals.erase(disabled_intervals.begin());
				}
				break;
			}
		}

		if(cnt < k[i]) {
			return 0;
		}

		disabled_intervals.insert(make_pair(r, k[i]));
	}

	return 1;
}

Compilation message

teams.cpp: In member function 'void MergeSortTree::build(const std::vector<int>&)':
teams.cpp:15:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   15 |   n = data.size();
      |       ~~~~~~~~~^~
teams.cpp: In member function 'int MergeSortTree::cnt_in_range(int, int, int, int, int, int, int)':
teams.cpp:33:55: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   33 |    return lower_bound(a[v].begin(), a[v].end(), high) - lower_bound(a[v].begin(), a[v].end(), low);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:120:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  if(total > students.size()) {
      |     ~~~~~~^~~~~~~~~~~~~~~~~
teams.cpp:130:6: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  128 |   int l = lower_bound(students.begin(), students.end(), make_pair(0, k[i]), [](pair<int, int> p1, pair<int, int> p2) {
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  129 |    return p1.second < p2.second;
      |    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  130 |   }) - students.begin();
      |   ~~~^~~~~~~~~~~~~~~~~~
teams.cpp:131:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   if(l == students.size()) {
      |      ~~^~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 23028 KB Output is correct
2 Correct 43 ms 23116 KB Output is correct
3 Correct 45 ms 23028 KB Output is correct
4 Correct 49 ms 23112 KB Output is correct
5 Correct 34 ms 23096 KB Output is correct
6 Correct 32 ms 23036 KB Output is correct
7 Correct 34 ms 23080 KB Output is correct
8 Correct 35 ms 23076 KB Output is correct
9 Correct 76 ms 23016 KB Output is correct
10 Correct 59 ms 23104 KB Output is correct
11 Correct 32 ms 23100 KB Output is correct
12 Correct 31 ms 23172 KB Output is correct
13 Correct 35 ms 23136 KB Output is correct
14 Correct 35 ms 23076 KB Output is correct
15 Correct 41 ms 23076 KB Output is correct
16 Correct 48 ms 23116 KB Output is correct
17 Correct 35 ms 23096 KB Output is correct
18 Correct 34 ms 23104 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 23012 KB Output is correct
2 Correct 50 ms 23096 KB Output is correct
3 Correct 332 ms 26000 KB Output is correct
4 Correct 45 ms 23096 KB Output is correct
5 Correct 244 ms 23124 KB Output is correct
6 Correct 229 ms 23128 KB Output is correct
7 Correct 40 ms 23084 KB Output is correct
8 Correct 176 ms 23104 KB Output is correct
9 Correct 80 ms 23124 KB Output is correct
10 Correct 191 ms 23104 KB Output is correct
11 Correct 240 ms 23144 KB Output is correct
12 Correct 519 ms 23048 KB Output is correct
13 Correct 606 ms 23252 KB Output is correct
14 Correct 433 ms 24624 KB Output is correct
15 Correct 278 ms 23424 KB Output is correct
16 Correct 260 ms 23224 KB Output is correct
17 Correct 273 ms 23128 KB Output is correct
18 Correct 272 ms 23312 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 119596 KB Output is correct
2 Correct 240 ms 119660 KB Output is correct
3 Correct 1241 ms 125524 KB Output is correct
4 Correct 236 ms 126636 KB Output is correct
5 Correct 1002 ms 124256 KB Output is correct
6 Correct 896 ms 124352 KB Output is correct
7 Correct 181 ms 124204 KB Output is correct
8 Correct 724 ms 124348 KB Output is correct
9 Correct 448 ms 124344 KB Output is correct
10 Correct 663 ms 122756 KB Output is correct
11 Correct 937 ms 123432 KB Output is correct
12 Correct 1534 ms 124128 KB Output is correct
13 Correct 1910 ms 125912 KB Output is correct
14 Correct 1633 ms 129508 KB Output is correct
15 Correct 877 ms 126824 KB Output is correct
16 Correct 931 ms 126908 KB Output is correct
17 Correct 837 ms 126268 KB Output is correct
18 Correct 764 ms 126348 KB Output is correct