oj.uz

답안 #133144

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
133144 2019-07-20T07:56:52 Z Mahdi_Jfri 팀들 (IOI15_teams) C++14
77 / 100
 832 ms 524292 KB 
#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

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.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12280 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct
3 Correct 13 ms 13048 KB Output is correct
4 Correct 14 ms 13176 KB Output is correct
5 Correct 13 ms 13140 KB Output is correct
6 Correct 14 ms 13176 KB Output is correct
7 Correct 13 ms 13176 KB Output is correct
8 Correct 14 ms 13176 KB Output is correct
9 Correct 13 ms 13048 KB Output is correct
10 Correct 13 ms 13048 KB Output is correct
11 Correct 13 ms 13048 KB Output is correct
12 Correct 13 ms 13052 KB Output is correct
13 Correct 13 ms 13104 KB Output is correct
14 Correct 14 ms 13176 KB Output is correct
15 Correct 16 ms 13048 KB Output is correct
16 Correct 16 ms 13176 KB Output is correct
17 Correct 13 ms 12408 KB Output is correct
18 Correct 12 ms 12408 KB Output is correct
19 Correct 12 ms 12412 KB Output is correct
20 Correct 13 ms 12408 KB Output is correct
21 Correct 13 ms 12360 KB Output is correct
22 Correct 16 ms 12408 KB Output is correct
23 Correct 17 ms 12380 KB Output is correct
24 Correct 13 ms 12408 KB Output is correct
25 Correct 12 ms 12408 KB Output is correct
26 Correct 13 ms 12408 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 197228 KB Output is correct
2 Correct 264 ms 197172 KB Output is correct
3 Correct 290 ms 197176 KB Output is correct
4 Correct 279 ms 197532 KB Output is correct
5 Correct 240 ms 195564 KB Output is correct
6 Correct 224 ms 195692 KB Output is correct
7 Correct 224 ms 195668 KB Output is correct
8 Correct 224 ms 195564 KB Output is correct
9 Correct 252 ms 195988 KB Output is correct
10 Correct 217 ms 195692 KB Output is correct
11 Correct 216 ms 195692 KB Output is correct
12 Correct 223 ms 195980 KB Output is correct
13 Correct 238 ms 196080 KB Output is correct
14 Correct 249 ms 196736 KB Output is correct
15 Correct 246 ms 196972 KB Output is correct
16 Correct 244 ms 197148 KB Output is correct
17 Correct 223 ms 195948 KB Output is correct
18 Correct 222 ms 196076 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 197484 KB Output is correct
2 Correct 272 ms 197468 KB Output is correct
3 Correct 337 ms 200892 KB Output is correct
4 Correct 265 ms 197484 KB Output is correct
5 Correct 359 ms 195816 KB Output is correct
6 Correct 334 ms 195820 KB Output is correct
7 Correct 228 ms 195772 KB Output is correct
8 Correct 330 ms 195828 KB Output is correct
9 Correct 218 ms 195996 KB Output is correct
10 Correct 221 ms 195756 KB Output is correct
11 Correct 224 ms 195900 KB Output is correct
12 Correct 476 ms 196076 KB Output is correct
13 Correct 433 ms 196376 KB Output is correct
14 Correct 362 ms 199256 KB Output is correct
15 Correct 261 ms 197136 KB Output is correct
16 Correct 271 ms 197388 KB Output is correct
17 Correct 248 ms 196140 KB Output is correct
18 Correct 241 ms 196332 KB Output is correct

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 832 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -