Submission #310905

#	Time	Username	Problem	Language	Result	Execution time	Memory
310905		johutha	Teams (IOI15_teams)	C++17	34 / 100	4093 ms	237408 KiB

teams

#include <iostream>
#include <vector>
#include "teams.h"
#include <algorithm>
#include <set>

using namespace std;

struct fenw
{
	int n;
	vector<set<pair<int,int>>> table;
	vector<int> cmp;

	void insert(int x, int y, int id)
	{
		x = lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
		for (; x <= n; x += (x & (-x)))
		{
			table[x].insert(make_pair(y, id));
		}
	}

	void erase(int x, int y, int id)
	{
		x = lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
		for (; x <= n; x += (x & (-x)))
		{
			table[x].erase(make_pair(y, id));
		}
	}

	pair<int,int> query(int s)
	{
		int x = upper_bound(cmp.begin(), cmp.end(), s) - cmp.begin();
		pair<int,int> res = make_pair(1e8, -1);
		for (; x; x -= (x & (-x)))
		{
			auto cand = table[x].lower_bound(make_pair(s, -1));
			if (cand != table[x].end()) res = min(res, *cand);
		}
		return res;
	}

	void reserve(int x)
	{
		cmp.push_back(x);
	}

	void pre()
	{
		sort(cmp.begin(), cmp.end());
		cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
		n = cmp.size();
		table.resize(n + 1);
	}
};

fenw fw;
vector<pair<int,int>> pnts;

void init(int n, int A[], int B[])
{
	for (int i = 0; i < n; i++)
	{
		pnts.emplace_back(A[i], B[i]);
		fw.reserve(A[i]);
	}
	fw.pre();
	for (int i = 0; i < n; i++)
	{
		fw.insert(A[i], B[i], i);
	}
}

int can(int m, int K[])
{
	vector<int> qs(m);

	for (int i = 0; i < m; i++)
	{
		qs[i] = K[i];
	}
	sort(qs.begin(), qs.end());

	vector<int> used;

	auto end = [&]()
	{
		for (auto i : used)
		{
			fw.insert(pnts[i].first, pnts[i].second, i);
		}
	};

	for (int cq = 0; cq < m; cq++)
	{
		int q = qs[cq];
		for (int i = 0; i < q; i++)
		{
			auto cr = fw.query(q);
			if (cr.second == -1)
			{
				end();
				return 0;
			}
			used.push_back(cr.second);
			fw.erase(pnts[cr.second].first, pnts[cr.second].second, cr.second);
		}
	}
	end();
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'void fenw::insert(int, int, int)':
teams.cpp:17:60: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   17 |   x = lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In member function 'void fenw::erase(int, int, int)':
teams.cpp:26:60: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   26 |   x = lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
      |       ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In member function 'std::pair<int, int> fenw::query(int)':
teams.cpp:35:50: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   35 |   int x = upper_bound(cmp.begin(), cmp.end(), s) - cmp.begin();
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In member function 'void fenw::pre()':
teams.cpp:54:15: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   54 |   n = cmp.size();
      |       ~~~~~~~~^~

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