Submission #292340

#	Time	Username	Problem	Language	Result	Execution time	Memory
292340		VodkaInTheJar	Teams (IOI15_teams)	C++14	100 / 100	3886 ms	149096 KiB

teams

#include <bits/stdc++.h>
 
using namespace std;

const int maxn = 5e5 + 3; 

vector <int> merge(vector <int> &a, vector <int> &b)
{
	vector <int> ans; 
	int pos_a = 0, pos_b = 0, sz_a = (int)a.size(), sz_b = (int)b.size();
	while (pos_a < sz_a && pos_b < sz_b)
	{
		if (a[pos_a] < b[pos_b])
		{
			ans.push_back(a[pos_a]);
			pos_a++;
		}
		
		else
		{
			ans.push_back(b[pos_b]);
			pos_b++;
		}
	}
	
	while (pos_a < sz_a)
	{
		ans.push_back(a[pos_a]);
		pos_a++;
	}
	
	while (pos_b < sz_b)
	{
		ans.push_back(b[pos_b]);
		pos_b++;
	}
	
	return ans; 
}

int n; 
vector <int> ve[maxn];
vector <int> tr[maxn * 4];
void build(int v, int l, int r)
{
	if (l == r)
	{
		tr[v] = ve[l];
		sort (tr[v].begin(), tr[v].end());
		return;
	}
	
	int mid = (l + r) / 2;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	
	tr[v] = merge(tr[v * 2], tr[v * 2 + 1]);
}

vector <int> temp; 
void get(int v, int l, int r, int ll, int rr)
{
	if (l > rr || r < ll)
	return;
	
	if (l >= ll && r <= rr)
	{
		temp.push_back(v);
		return; 
	}
	
	int mid = (l + r) / 2;
	get(v * 2, l, mid, ll, rr);
	get(v * 2 + 1, mid + 1, r, ll, rr);
}

void init(int _n, int l[], int r[])
{
	n = _n;
	for (int i = 1; i <= n; i++)
	ve[l[i-1]].push_back(r[i-1]);
	
	build(1, 1, n);
}

int cnt[maxn];
bool can(int m, int k[])
{
	long long sum = 0;
	for (int i = 0; i < m; i++)
	sum += k[i];
	
	if (sum > n)
	return false;
	
	 map <int, int> mp;
	 for (int i = 0; i < m; i++)
	 mp[k[i]]++;
	 
	 for (int i = 0; i < (int)mp.size(); i++)
	 cnt[i] = 0;
	 
	 int idx = 0; 
	 for (auto it = mp.begin(); it != mp.end(); it++)
	 {
		 int prv = 1;
		 if (it != mp.begin())
		 prv = prev(it)->first + 1;
		 
		 temp.clear();
		 get(1, 1, n, prv, it->first);
		 
		 int curr_idx = idx; 
		 for (auto it1 = it; it1 != mp.end(); it1++)
		 {
			 int nxt = n;
			 if (it1 != prev(mp.end()))
			 nxt = next(it1)->first - 1; 
			 
			 for (auto i: temp)
			 {
				 auto it2 = lower_bound(tr[i].begin(), tr[i].end(), it1->first);
				 auto it3 = upper_bound(tr[i].begin(), tr[i].end(), nxt);
				 cnt[curr_idx] += it3 - it2; 	 
			 } 
			 
			 curr_idx++;
		 }
		 
		 int to_sub = it->second * it->first;
		 for (int i = idx; i < (int)mp.size() && to_sub; i++)
		 {
			 int curr_to_sub = min(cnt[i], to_sub);
			 to_sub -= curr_to_sub;
			 cnt[i] -= curr_to_sub; 
		 }
		 
		 if (to_sub)
		 return false;
		 
		 idx++;
	 }
	 
	 return true; 
}

Compilation message (stderr)

teams.cpp: In function 'bool can(int, int*)':
teams.cpp:124:29: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  124 |      cnt[curr_idx] += it3 - it2;
      |                             ^~~

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