Submission #484890

#	Time	Username	Problem	Language	Result	Execution time	Memory
484890		imachug	Teams (IOI15_teams)	C++17	77 / 100	4042 ms	126172 KiB

teams

#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 = 0;
		while(l < students.size() && students[l].second < k[i]) {
			l++;
		}

		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 (stderr)

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:129:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   while(l < students.size() && students[l].second < k[i]) {
      |         ~~^~~~~~~~~~~~~~~~~
teams.cpp:133: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]
  133 |   if(l == students.size()) {
      |      ~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23