Submission #133084

#	Time	Username	Problem	Language	Result	Execution time	Memory
133084		Mahdi_Jfri	Teams (IOI15_teams)	C++14	34 / 100	4025 ms	130512 KiB

teams

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 5e5 + 20;
const int maxb = 20;

int dp[maxn] , n , l[maxn] , r[maxn];

int seg[maxb][maxn] , lpt[maxb][maxn] , rpt[maxb][maxn];

void f(int &val , int s , int e , int h)
{
	val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h];
}

void build(int s = 0 , int e = n , int h = 0)
{
	if(e - s < 2)
	{
		seg[h][s] = l[s];
		return;
	}

	int m = (s + e) / 2;
	build(s , m , h + 1);
	build(m , e , h + 1);

	merge(seg[h + 1] + s , seg[h + 1] + m , seg[h + 1] + m , seg[h + 1] + e , seg[h] + s);
	for(int i = s; i < e; i++)
	{
		lpt[h][i] = lower_bound(seg[h + 1] + s , seg[h + 1] + m , seg[h][i]) - seg[h + 1];
		if(lpt[h][i] == m)
			lpt[h][i] = maxn;
		rpt[h][i] = lower_bound(seg[h + 1] + m , seg[h + 1] + e , seg[h][i]) - seg[h + 1];
		if(rpt[h][i] == e)
			rpt[h][i] = maxn;
	}
}

int get(int l , int r , int val , int s = 0 , int e = n , int h = 0)
{
	if(!h)
	{
		val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h];
		if(val == e)
			val = maxn;
	}

	if(val >= maxn)
		return 0;

	if(l <= s && e <= r)
		return e - val;
	if(r <= s || e <= l)
		return 0;

	int m = (s + e) / 2;
	return get(l , r , lpt[h][val] , s , m , h + 1) + get(l , r , rpt[h][val] , m , e , h + 1);
}

void init(int N, int a[], int b[])
{
	n = N;

	vector<pair<int , int> > tmp;
	for(int i = 0; i < n; i++)
	{
		l[i] = a[i] , r[i] = b[i];
		tmp.pb({r[i] , -l[i]});
	}

	sort(tmp.begin() , tmp.end());
	for(int i = 0; i < n; i++)
		l[i] = -tmp[i].second , r[i] = tmp[i].first;

	build();
}

int p[maxn] , t[maxn];

int can(int m, int k[])
{
	sort(k , k + m);

	for(int i = 0; i < m; i++)
		t[k[i]] = 0;

	int sum = 0;
	for(int i = 1; i <= m; i++)
	{
		p[i] = k[i - 1];
		sum += p[i];
		if(sum > n)
			return 0;
		t[p[i]]++;
	}

	m = unique(p + 1 , p + m + 1) - p - 1;

	p[0] = 0;
	dp[0] = 0;
	for(int i = 1; i <= m; i++)
	{
		dp[i] = -1e9;

		int x = lower_bound(r , r + n , p[i]) - r;
		for(int j = i - 1; j >= 0; j--)
			dp[i] = max(dp[i] , dp[j] + get(0 , x , p[j] + 1));

		dp[i] += t[p[i]] * p[i];
		if(dp[i] + get(0 , n , p[i] + 1) - n > 0)
			return 0;
	}

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void f(int&, int, int, int)':
teams.cpp:18:51: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h];
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
teams.cpp: In function 'void build(int, int, int)':
teams.cpp:36:72: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   lpt[h][i] = lower_bound(seg[h + 1] + s , seg[h + 1] + m , seg[h][i]) - seg[h + 1];
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp:39:72: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   rpt[h][i] = lower_bound(seg[h + 1] + m , seg[h + 1] + e , seg[h][i]) - seg[h + 1];
               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
teams.cpp: In function 'int get(int, int, int, int, int, int)':
teams.cpp:45:68: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 int get(int l , int r , int val , int s = 0 , int e = n , int h = 0)
                                                                    ^
teams.cpp:12:30: note: shadowed declaration is here
 int dp[maxn] , n , l[maxn] , r[maxn];
                              ^
teams.cpp:45:68: warning: declaration of 'l' shadows a global declaration [-Wshadow]
 int get(int l , int r , int val , int s = 0 , int e = n , int h = 0)
                                                                    ^
teams.cpp:12:20: note: shadowed declaration is here
 int dp[maxn] , n , l[maxn] , r[maxn];
                    ^
teams.cpp:49:52: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h];
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:103:36: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  m = unique(p + 1 , p + m + 1) - p - 1;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:111:41: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
   int x = lower_bound(r , r + n , p[i]) - r;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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