Submission #133094

#	Time	Username	Problem	Language	Result	Execution time	Memory
133094		Mahdi_Jfri	Teams (IOI15_teams)	C++14	13 / 100	662 ms	130320 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 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);

	int pt1 = s , pt2 = m , pt = s;
	while(pt != e)
	{
		if(pt2 == e || (pt1 < m && seg[h + 1][pt1] < seg[h + 1][pt2]))
		{
			lpt[h][pt] = pt1;

			if(pt2 == e)
				rpt[h][pt] = maxn;
			else
				rpt[h][pt] = pt2;

			seg[h][pt] = seg[h + 1][pt1++];
		}
		else
		{
			rpt[h][pt] = pt2;
			if(pt1 == m)
				lpt[h][pt] = maxn;
			else
				lpt[h][pt] = pt1;

			seg[h][pt] = seg[h + 1][pt2++];
		}
		pt++;
	}
}

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;

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

		int x = lower_bound(r , r + n , p[i]) - r;

		pair<int, int> ans = {-1e9 , i};
		for(int j = i - 1; j >= PT; j--)
			ans = max(ans , make_pair(dp[j] + get(0 , x , p[j] + 1) , j));

		dp[i] = ans.first;
		PT = ans.second;

		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 'int get(int, int, int, int, int, int)':
teams.cpp:56: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:56: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:60: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:114:36: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  m = unique(p + 1 , p + m + 1) - p - 1;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:124: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: 0 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23