Submission #45877

#	Time	Username	Problem	Language	Result	Execution time	Memory
45877		RayaBurong25_1	Teams (IOI15_teams)	C++17	100 / 100	3986 ms	420536 KiB

teams

#include "teams.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
#define INF 1000000007
typedef struct point point;
struct point
{
	int a, b;
};
typedef struct node node;
struct node
{
	int sum;
	node* l;
	node* r;
};
int n;
node* root[500005];
int whichroot[500005];
int sortAB(point a, point b)
{
	return (a.a < b.a || (a.a == b.a && a.b < b.b));
}
int max(int a, int b)
{
	return (a > b)?a:b;
}
int min(int a, int b)
{
	return (a < b)?a:b;
}
node* makeTree(int s, int e)
{
	// printf("makeTree %d %d\n", s, e);
	if (s == e)
	{
		node* p = new node();
		p->sum = 0;
		p->l = NULL;
		p->r = NULL;
		return p;
	}
	int m = (s + e)/2;
	node* p = new node();
	p->sum = 0;
	p->l = makeTree(s, m);
	p->r = makeTree(m + 1, e);
	return p;
}
node* update(node* p, int s, int e, int v)
{
	// printf("update p%p s%d e%d v%d\n", p, s, e, v);
	if (s == e)
	{
		node* q = new node();
		q->sum = p->sum + 1;
		q->l = NULL;
		q->r = NULL;
		return q;
	}
	int m = (s + e)/2;
	node* q = new node();
	if (v <= m)
	{
		q->l = update(p->l, s, m, v);
		q->r = p->r;
	}
	else
	{
		q->l = p->l;
		q->r = update(p->r, m + 1, e, v);
	}
	q->sum = q->l->sum + q->r->sum;
	return q;
}
void init(int N, int A[], int B[])
{
	n = N;
	std::vector<point> P;
	int i;
	for (i = 0; i < N; i++)
		P.push_back({A[i], B[i]});
	std::sort(P.begin(), P.end(), sortAB);
	root[0] = makeTree(1, N);
	for (i = 1; i <= N; i++)
	{
		root[i] = update(root[i - 1], 1, N, P[i - 1].b);
		whichroot[P[i - 1].a] = i;
	}
	for (i = 1; i <= N; i++)
		whichroot[i] = max(whichroot[i], whichroot[i - 1]);
	// printf("init ok\n");
}
std::vector<std::pair<std::pair<int, int>, int> > Stairs;
int query(int Xmn, int Xmx, int Y)
{
	// printf("query Xmn%d Xmx%d Y%d\n", Xmn, Xmx, Y);
	if (Y < 1)
		return 0;
	node* p = root[whichroot[Xmx]];
	node* q = root[whichroot[Xmn]];
	int s = 1, e = n;
	int m, r = 0;
	while (s != e)
	{
		m = (s + e)/2;
		if (Y <= m)
		{
			p = p->l;
			q = q->l;
			e = m;
		}
		else
		{
			r += p->l->sum - q->l->sum;
			p = p->r;
			q = q->r;
			s = m + 1;
		}
	}
	r += p->sum - q->sum;
	return r;
}
int compStair(std::pair<std::pair<int, int>, int> e, int v)
{
	return e.first.second > v;
}
int sumBoys(int Xmx, int Y)
{
	// printf("sumBoys Xmx%d Y%d\n", Xmx, Y);
	int i;
	i = std::lower_bound(Stairs.begin(), Stairs.end(), Y, compStair) - Stairs.begin();
	i--;
	int Xmn = Stairs[i].first.first;
	// printf("Xmn %d\n", Xmn);
	int Q = query(Xmn, Xmx, Y) - (Stairs.back().second - Stairs[i].second);
	// printf("Q %d\n", Q);
	return Q;
}
void updStairs(int X, int Y, int K)
{
	int sum = 0;
	while (Stairs.back().first.second <= Y)
	{
		sum += Stairs.back().second;
		Stairs.pop_back();
		sum -= Stairs.back().second;
	}
	Stairs.push_back({{X, Y}, Stairs.back().second + sum + K});
	// int i;
	// for (i = 0; i < Stairs.size(); i++)
		// printf("Stairs %d %d %d\n", Stairs[i].first.first, Stairs[i].first.second, Stairs[i].second);
}
int can(int M, int K[])
{
	std::sort(&K[0], &K[M]);
	Stairs.clear();
	Stairs.push_back({{0, INF}, 0});
	int i;
	int mn, md, mx;
	int sb, kisb;
	for (i = 0; i < M; i++)
	{
		mn = K[i] - 1;
		mx = n;
		sb = sumBoys(K[i], mn);
		if (sumBoys(K[i], mx) < K[i] + sb)
			return 0;
		kisb = K[i] + sb;
		while (1)
		{
			// printf("mn %d mx %d\n", mn, mx);
			if (mx - mn <= 1)
			{
				md = mx;
				break;
			}
			md = (mn + mx)/2;
			if (sumBoys(K[i], md) >= kisb)
				mx = md;
			else
				mn = md;
		}
		updStairs(K[i], md, kisb);
	}
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int sumBoys(int, int)':
teams.cpp:133:67: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<std::pair<int, int>, int>*, std::vector<std::pair<std::pair<int, int>, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
  i = std::lower_bound(Stairs.begin(), Stairs.end(), Y, compStair) - Stairs.begin();
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

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