Submission #133144

#	Time	Username	Problem	Language	Result	Execution time	Memory
133144		Mahdi_Jfri	Teams (IOI15_teams)	C++14	77 / 100	832 ms	524292 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 sq = 400;
const int maxb = 20;

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

int seg[maxb][maxn] , lpt[maxb][maxn] , rpt[maxb][maxn] , cnt[sq + 5][maxn];

vector<int> shit[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++;
	}
}

inline int get(int r , int val , int s = 0 , int e = n , int h = 0)
{
	int ans = 0;
	val = lower_bound(seg[h] + s , seg[h] + e , val) - seg[h];
	if(val == e)
		return 0;

	while(1)
	{
		if(val >= maxn)
			return ans;

		if(e <= r)
			return ans + e - val;
		if(r <= s)
			return ans;

		int m = (s + e) / 2;
		if(r <= m)
			val = lpt[h][val] , e = m , h++;
		else
		{
			ans += max(0 , m - lpt[h][val]);
			val = rpt[h][val] , s = m , h++;
		}
	}
}

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;
		shit[l[i]].pb(r[i]);
	}

	build();

	for(int i = sq; i >= 1; i--)
	{
		int pt = 0 , t = 0;
		for(int j = i; j <= n; j++)
		{
			if(i == sq)
			{
				while(pt < n && r[pt] <= j)
					t += (l[pt++] >= i);
				cnt[i][j] = t;
			}
			else
			{
				while(pt < (int)shit[i].size() && shit[i][pt] <= j)
					pt++;
				cnt[i][j] = cnt[i + 1][j] + pt;
			}
		}
	}
}

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--)
		{
			if(p[j] + 1 <= sq)
				dp[i] = max(dp[i] , dp[j] + cnt[p[j] + 1][p[i] - 1]);
			else
				dp[i] = max(dp[i] , dp[j] + get(x , p[j] + 1));
		}

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

	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int get(int, int, int, int, int)':
teams.cpp:59:67: warning: declaration of 'r' shadows a global declaration [-Wshadow]
 inline int get(int r , int val , int s = 0 , int e = n , int h = 0)
                                                                   ^
teams.cpp:13:30: note: shadowed declaration is here
 int dp[maxn] , n , l[maxn] , r[maxn];
                              ^
teams.cpp:62: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 'int can(int, int*)':
teams.cpp:147:36: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
  m = unique(p + 1 , p + m + 1) - p - 1;
      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:156: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: 43 / 43
• Subtask 4: 0 / 23