Submission #541100

#	Time	Username	Problem	Language	Result	Execution time	Memory
541100		GioChkhaidze	Teams (IOI15_teams)	C++14	100 / 100	1402 ms	146072 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define pb push_back
#define f first
#define s second

using namespace std;

const int Nn = 5e5 + 5;

bool used[Nn];
int n, m, cost, a[Nn], b[Nn], k[Nn], dp[Nn], pr[Nn], nx[Nn], mpr[Nn];
vector < int > v[4* Nn], O[Nn];

void build(tree) {
	if (l == r) {
		v[h] = O[l];
		return;
	}
	build(left), build(right);
	int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
	while (li < ls || ri < rs) {
		if (li < ls && (ri == rs || v[lf][li] <= v[rf][ri])) {
			v[h].pb(v[lf][li++]);
		}
			else
		if (ri < rs && (li == ls || v[rf][ri] <= v[lf][li])) {
			v[h].pb(v[rf][ri++]);
		}
	} 
}

int Mn, Mx, id;
int g(int h) {
	int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
	int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
	return max(0, r - l);
} 

int get(tree) {
	if (l == r) return g(h);
	if (Mx <= mf) return get(left) + g(rf);
	return get(right);
}

int Get(tree, int vl) {
	if (l == r) {
		if (g(h) <= vl) return l;
		return n + 1;
	}
	int rc = g(rf);
	if (rc <= vl) 
		return min(mf + 1, Get(left, vl - rc));
	return Get(right, vl); 
}

int Mm(int tl, int tr) {
	/*int l = k[tr] + 1, r = n, res = n + 1, mid;
	while (l <= r) {
		mid = ((l + r) >> 1), Mx = mid;
		Mn = k[tl] + 1;
		int I = dp[tl] + get(1, 1, n);
		Mn = k[tr] + 1;
		int J = dp[tr] + get(1, 1, n);
		if (I <= J) 
			res = mid, r = mid - 1;
				else 
			l = mid + 1;
	}
	return res;*/
	Mn = k[tl] + 1, Mx = k[tr];
	return Get(1, 1, n, dp[tr] - dp[tl]);
}

/*
i < j
dp[i] + solve(i, k) <= dp[j] + solve(j, k);

dp[j] - dp[i] >= solve(i, k) - solve(j, k)

mid = {k[j] + 1, n}

dp[j] - dp[i] >= solve(i, mid) - solve(j, mid)

max number of a,b such that a in (k[i] + 1, k[j])  b in (k[mid], n)

how many a,b   a in (k[i] + 1, k[k])  b in (k[k], n)
how many a,b   a in (k[j] + 1, k[k])  b in (k[k], n)
*/

void init(int N, int A[], int B[]) {
	n = N;
	for (int i = 1; i <= n; ++i) {
		a[i] = A[i - 1];
		b[i] = B[i - 1];
		O[b[i]].pb(a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		sort(O[i].begin(), O[i].end());
	}
	build(1, 1, n);
}

int can(int M, int K[]) {
	m = M;
	ll sum = 0;
	for (int i = 1; i <= m; ++i) {
		pr[i] = nx[i] = used[i] = 0;
		k[i] = K[i - 1];
		sum += k[i];
	}
	sort(k + 1, k + m + 1);
	if (sum > n) return 0;
	set < pair < int , int > > st;
	vector < int > dq;
	dq.push_back(0);
	// get(1, 1, n);
	// how many a,b   a in (k[l] + 1, k[i])  b in (k[i], n)
	for (int i = 1; i <= m; ++i) {
		while (st.size() && (*st.begin()).f <= k[i]) {
			int mo = (*st.begin()).f;
			int id = (*st.begin()).s;
			st.erase(st.find({mo, id}));
			used[id] = true;
			// was erased pr[id] -> id
			int tl = pr[id], tr = nx[id];
			if (tr) {
				// erase id -> nx[id]
				st.erase({mpr[tr], tr});
				mpr[tr] = Mm(tl, tr);
				// insert pr[id] -> nx[id]
				st.insert({mpr[tr], tr});
				nx[tl] = tr, pr[tr] = tl;
			}
		}
		// find dp[i];
		while (used[dq.back()]) {
			dq.pop_back();
		}
		int l = dq.back();
		Mn = k[l] + 1, Mx = k[i];
		//if (Mn <= Mx) 
		cost = get(1, 1, n);
		//		else 
		//	cost = 0;
		dp[i] = dp[l] - k[i] + cost;
		if (dp[i] < 0) return false;
		dq.push_back(i);
		mpr[i] = Mm(l, i);
		pr[i] = l, nx[l] = i;
		st.insert({mpr[i], i});
	}
	return true;
}

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:29:38: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |  int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
      |                            ~~~~~~~~~~^~
teams.cpp:29:57: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   29 |  int li = 0, ri = 0, ls =  v[lf].size(), rs = v[rf].size();
      |                                               ~~~~~~~~~~^~
teams.cpp: In function 'int g(int)':
teams.cpp:43:53: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   43 |  int l = (lower_bound(v[h].begin(), v[h].end(), Mn) - v[h].begin());
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp:44:57: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   44 |  int r = (lower_bound(v[h].begin(), v[h].end(), Mx + 1) - v[h].begin());
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:130:8: warning: declaration of 'id' shadows a global declaration [-Wshadow]
  130 |    int id = (*st.begin()).s;
      |        ^~
teams.cpp:41:13: note: shadowed declaration is here
   41 | int Mn, Mx, id;
      |             ^~

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