oj.uz

Submission #66494

# Submission time Handle Problem Language Result Execution time Memory
66494 2018-08-11T01:19:13 Z qkxwsm Teams (IOI15_teams) C++17
77 / 100
 4000 ms 380912 KB 
#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

template<class T>
void readi(T &x)
{
	T input = 0;
	bool negative = false;
	char c = ' ';
	while (c < '-')
	{
		c = getchar();
	}
	if (c == '-')
	{
		negative = true;
		c = getchar();
	}
	while (c >= '0')
	{
		input = input * 10 + (c - '0');
		c = getchar();
	}
	if (negative)
	{
		input = -input;
	}
	x = input;
}
template<class T>
void printi(T output)
{
	if (output == 0)
	{
		putchar('0');
		return;
	}
	if (output < 0)
	{
		putchar('-');
		output = -output;
	}
	int aout[20];
	int ilen = 0;
	while(output)
	{
		aout[ilen] = ((output % 10));
		output /= 10;
		ilen++;
	}
	for (int i = ilen - 1; i >= 0; i--)
	{
		putchar(aout[i] + '0');
	}
	return;
}
template<class T>
void ckmin(T &a, T b)
{
	a = min(a, b);
}
template<class T>
void ckmax(T &a, T b)
{
	a = max(a, b);
}
long long randomize(long long mod)
{
	return ((1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod;
}

#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second

const long double PI = 4.0 * atan(1.0);
const long double EPS = 1e-20;

#define MAGIC 347
#define SINF 10007
#define CO 1000007
#define INF 1000000007
#define BIG 1000000931
#define LARGE 1696969696967ll
#define GIANT 2564008813937411ll
#define LLINF 2696969696969696969ll
#define MAXN 500013

long long normalize(long long x, long long mod = INF)
{
	return (((x % mod) + mod) % mod);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, M, K;
pii want[MAXN];
pii arr[MAXN];
int dp[MAXN];
int T;

struct node
{
	node *ch[2];
	int sum;
	node()
	{
		ch[0] = ch[1] = nullptr;
		sum = 0;
	}
};
node *root[MAXN];
int ft[MAXN];

node* initpseg(int L, int R)
{
	node *t = new node();
	if (L == R)
	{
		return t;
	}
	int mid = (L + R) / 2;
	t -> ch[0] = initpseg(L, mid);
	t -> ch[1] = initpseg(mid + 1, R);
	return t;
}
node* update(node *w, int L, int R, int x, int v)
{
	if (x < L || R < x)
	{
		return w;
	}
	node *t = new node();
	if (L == R)
	{
		t -> sum = w -> sum + v;
		t -> ch[0] = t -> ch[1] = nullptr;
		return t;
	}
	int mid = (L + R) / 2;
	t -> ch[0] = update(w -> ch[0], L, mid, x, v);
	t -> ch[1] = update(w -> ch[1], mid + 1, R, x, v);
	t -> sum = t -> ch[0] -> sum + t -> ch[1] -> sum;
	return t;
}
int query(node *t, int L, int R, int a, int b)
{
	if (b < L || R < a)
	{
		return 0;
	}
	if (a <= L && R <= b)
	{
		return t -> sum;
	}
	int mid = (L + R) / 2;
	return query(t -> ch[0], L, mid, a, b) + query(t -> ch[1], mid + 1, R, a, b);
}
int rect(int X1, int X2, int Y1, int Y2)
{
	return query(root[ft[X2]], 0, N, Y1, Y2) - query(root[ft[X1 - 1]], 0, N, Y1, Y2);
}
int cost(int L, int R)
{
	return (rect(arr[L].fi + 1, arr[R].fi, arr[R].fi, N));
}
int overpass(int a, int b)
{
	//when does a become a better choice then b
	int lo = b + 1, hi = K;
	while(hi > lo)
	{
		int mid = (hi + lo) / 2;
		if (dp[a] + cost(a, mid) <= dp[b] + cost(b, mid))
		{
			//a is better than b
			hi = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}
	return lo;
}
void init(int n, int A[], int B[])
{
	N = n;
	for (int i = 0; i < N; i++)
	{
		want[i] = MP(A[i], B[i]);
	}
	sort(want, want + N);
	root[0] = initpseg(0, N);
	T = 1;
	for (int i = 0; i < N; i++)
	{
		if (i)
		{
			for (int j = want[i - 1].fi; j < want[i].fi; j++)
			{
				ft[j] = T - 1;
			}
		}
		else
		{
			for (int j = 0; j < want[i].fi; j++)
			{
				ft[j] = T - 1;
			}
		}
		ft[want[i].fi] = T;
		root[T] = update(root[T - 1], 0, N, want[i].se, 1);
		T++;
	}
	for (int j = want[N - 1].fi; j <= N; j++)
	{
		ft[j] = T - 1;
	}
}
int can(int m, int a[])
{
	M = m;
	int s = 0;
	for (int i = 0; i < M; i++)
	{
		s += a[i];
	}
	if (s > N)
	{
		return 0;
	}
	sort(a, a + M);
	K = 1;
	arr[0] = {0, 0};
	for (int i = 0; i < M; i++)
	{
		if (i == 0 || a[i] != a[i - 1])
		{
			arr[K] = MP(a[i], 1);
			K++;
		}
		else
		{
			arr[K - 1].se++;
		}
	}
	deque<int> opt;
	opt.PB(0);
	for (int i = 1; i < K; i++)
	{
		int sz = arr[i].fi;
		dp[i] = INF;
		while(opt.size() >= 2 && overpass(opt[opt.size() - 2], opt[opt.size() - 1]) <= i)
		{
			opt.pop_back();
		}
		int j = opt.back();
		ckmin(dp[i], dp[j] + cost(j, i));
		dp[i] -= arr[i].fi * arr[i].se;
		while(opt.size() >= 2 && overpass(opt[opt.size() - 2], opt[opt.size() - 1]) <= overpass(opt[opt.size() - 1], i))
		{
			opt.pop_back();
		}
		opt.PB(i);
	}
	for (int i = 0; i < K; i++)
	{
		if (dp[i] < 0)
		{
			return 0;
		}
	}
	//|neighbors| - |sum of #s| < 0 => die
	//there are at most sqrtN distinct guys
	return 1;
	//check if the sum of values in subset of k's is < sum cnt's of those k's
	//you need to make a team if
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:261:7: warning: unused variable 'sz' [-Wunused-variable]
   int sz = arr[i].fi;
       ^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 560 KB Output is correct
4 Correct 5 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 572 KB Output is correct
7 Correct 3 ms 572 KB Output is correct
8 Correct 3 ms 592 KB Output is correct
9 Correct 4 ms 592 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 636 KB Output is correct
13 Correct 3 ms 636 KB Output is correct
14 Correct 3 ms 636 KB Output is correct
15 Correct 3 ms 636 KB Output is correct
16 Correct 3 ms 636 KB Output is correct
17 Correct 3 ms 636 KB Output is correct
18 Correct 3 ms 636 KB Output is correct
19 Correct 2 ms 636 KB Output is correct
20 Correct 2 ms 652 KB Output is correct
21 Correct 3 ms 652 KB Output is correct
22 Correct 2 ms 652 KB Output is correct
23 Correct 3 ms 652 KB Output is correct
24 Correct 3 ms 652 KB Output is correct
25 Correct 2 ms 652 KB Output is correct
26 Correct 3 ms 652 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 65196 KB Output is correct
2 Correct 178 ms 65196 KB Output is correct
3 Correct 181 ms 65196 KB Output is correct
4 Correct 203 ms 65368 KB Output is correct
5 Correct 141 ms 65368 KB Output is correct
6 Correct 136 ms 65368 KB Output is correct
7 Correct 145 ms 65368 KB Output is correct
8 Correct 141 ms 65368 KB Output is correct
9 Correct 129 ms 65368 KB Output is correct
10 Correct 137 ms 66172 KB Output is correct
11 Correct 125 ms 66172 KB Output is correct
12 Correct 141 ms 66172 KB Output is correct
13 Correct 132 ms 66172 KB Output is correct
14 Correct 141 ms 66172 KB Output is correct
15 Correct 176 ms 66172 KB Output is correct
16 Correct 174 ms 66172 KB Output is correct
17 Correct 135 ms 66172 KB Output is correct
18 Correct 125 ms 66172 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 66172 KB Output is correct
2 Correct 1217 ms 66172 KB Output is correct
3 Correct 379 ms 68308 KB Output is correct
4 Correct 170 ms 68308 KB Output is correct
5 Correct 533 ms 68308 KB Output is correct
6 Correct 589 ms 68308 KB Output is correct
7 Correct 1687 ms 68308 KB Output is correct
8 Correct 919 ms 68968 KB Output is correct
9 Correct 132 ms 68968 KB Output is correct
10 Correct 135 ms 71456 KB Output is correct
11 Correct 217 ms 72496 KB Output is correct
12 Correct 845 ms 73552 KB Output is correct
13 Correct 777 ms 74908 KB Output is correct
14 Correct 462 ms 76980 KB Output is correct
15 Correct 475 ms 77424 KB Output is correct
16 Correct 471 ms 78740 KB Output is correct
17 Correct 453 ms 81096 KB Output is correct
18 Correct 410 ms 82448 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3893 ms 375088 KB Output is correct
2 Correct 3803 ms 375100 KB Output is correct
3 Correct 1825 ms 380912 KB Output is correct
4 Correct 1131 ms 380912 KB Output is correct
5 Correct 1872 ms 380912 KB Output is correct
6 Correct 2031 ms 380912 KB Output is correct
7 Execution timed out 4073 ms 380912 KB Time limit exceeded
8 Halted 0 ms 0 KB -