oj.uz

Submission #292340

# Submission time Handle Problem Language Result Execution time Memory
292340 2020-09-06T20:47:59 Z VodkaInTheJar Teams (IOI15_teams) C++14
100 / 100
 3886 ms 149096 KB 
#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

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.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 75120 KB Output is correct
2 Correct 115 ms 74992 KB Output is correct
3 Correct 114 ms 74992 KB Output is correct
4 Correct 115 ms 75252 KB Output is correct
5 Correct 65 ms 69360 KB Output is correct
6 Correct 62 ms 69488 KB Output is correct
7 Correct 61 ms 69492 KB Output is correct
8 Correct 61 ms 69360 KB Output is correct
9 Correct 64 ms 68464 KB Output is correct
10 Correct 62 ms 68212 KB Output is correct
11 Correct 62 ms 68208 KB Output is correct
12 Correct 65 ms 68544 KB Output is correct
13 Correct 73 ms 70296 KB Output is correct
14 Correct 87 ms 71592 KB Output is correct
15 Correct 107 ms 74612 KB Output is correct
16 Correct 107 ms 74480 KB Output is correct
17 Correct 64 ms 69588 KB Output is correct
18 Correct 64 ms 69624 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 75472 KB Output is correct
2 Correct 147 ms 75376 KB Output is correct
3 Correct 285 ms 78704 KB Output is correct
4 Correct 119 ms 75248 KB Output is correct
5 Correct 807 ms 70128 KB Output is correct
6 Correct 802 ms 69868 KB Output is correct
7 Correct 89 ms 69744 KB Output is correct
8 Correct 613 ms 69744 KB Output is correct
9 Correct 62 ms 68592 KB Output is correct
10 Correct 63 ms 68336 KB Output is correct
11 Correct 77 ms 68720 KB Output is correct
12 Correct 694 ms 69012 KB Output is correct
13 Correct 674 ms 71068 KB Output is correct
14 Correct 367 ms 75968 KB Output is correct
15 Correct 182 ms 74992 KB Output is correct
16 Correct 183 ms 74992 KB Output is correct
17 Correct 138 ms 70012 KB Output is correct
18 Correct 125 ms 69916 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 143592 KB Output is correct
2 Correct 596 ms 143456 KB Output is correct
3 Correct 1008 ms 149096 KB Output is correct
4 Correct 514 ms 143224 KB Output is correct
5 Correct 3886 ms 114408 KB Output is correct
6 Correct 3783 ms 114396 KB Output is correct
7 Correct 208 ms 114384 KB Output is correct
8 Correct 3019 ms 114492 KB Output is correct
9 Correct 165 ms 109864 KB Output is correct
10 Correct 166 ms 107964 KB Output is correct
11 Correct 595 ms 108620 KB Output is correct
12 Correct 2662 ms 110260 KB Output is correct
13 Correct 2245 ms 119620 KB Output is correct
14 Correct 1343 ms 143016 KB Output is correct
15 Correct 619 ms 137960 KB Output is correct
16 Correct 623 ms 137964 KB Output is correct
17 Correct 329 ms 114844 KB Output is correct
18 Correct 336 ms 114648 KB Output is correct