oj.uz

Submission #151790

# Submission time Handle Problem Language Result Execution time Memory
151790 2019-09-04T17:40:13 Z qkxwsm Teams (IOI15_teams) C++14
77 / 100
 4000 ms 372812 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, T;
pii want[MAXN];
pii arr[MAXN];
int dp[MAXN];

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:260: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 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 3 ms 360 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 380 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 4 ms 364 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 404 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 380 KB Output is correct
14 Correct 3 ms 380 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 65872 KB Output is correct
2 Correct 179 ms 65912 KB Output is correct
3 Correct 192 ms 65908 KB Output is correct
4 Correct 186 ms 66564 KB Output is correct
5 Correct 151 ms 65528 KB Output is correct
6 Correct 139 ms 65528 KB Output is correct
7 Correct 143 ms 65460 KB Output is correct
8 Correct 143 ms 65656 KB Output is correct
9 Correct 125 ms 63608 KB Output is correct
10 Correct 130 ms 66296 KB Output is correct
11 Correct 132 ms 66296 KB Output is correct
12 Correct 137 ms 66408 KB Output is correct
13 Correct 140 ms 66552 KB Output is correct
14 Correct 137 ms 64376 KB Output is correct
15 Correct 169 ms 65884 KB Output is correct
16 Correct 172 ms 65856 KB Output is correct
17 Correct 138 ms 66808 KB Output is correct
18 Correct 138 ms 66724 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 66756 KB Output is correct
2 Correct 1016 ms 66664 KB Output is correct
3 Correct 351 ms 70136 KB Output is correct
4 Correct 174 ms 66448 KB Output is correct
5 Correct 542 ms 66420 KB Output is correct
6 Correct 569 ms 66424 KB Output is correct
7 Correct 1581 ms 66464 KB Output is correct
8 Correct 800 ms 66436 KB Output is correct
9 Correct 128 ms 63508 KB Output is correct
10 Correct 134 ms 66780 KB Output is correct
11 Correct 171 ms 67012 KB Output is correct
12 Correct 809 ms 67272 KB Output is correct
13 Correct 674 ms 67644 KB Output is correct
14 Correct 419 ms 68228 KB Output is correct
15 Correct 452 ms 66772 KB Output is correct
16 Correct 440 ms 66776 KB Output is correct
17 Correct 435 ms 67508 KB Output is correct
18 Correct 396 ms 67676 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3483 ms 366064 KB Output is correct
2 Correct 3409 ms 365936 KB Output is correct
3 Correct 1643 ms 372812 KB Output is correct
4 Correct 1085 ms 365544 KB Output is correct
5 Correct 1820 ms 363260 KB Output is correct
6 Correct 1932 ms 363312 KB Output is correct
7 Execution timed out 4099 ms 363296 KB Time limit exceeded
8 Halted 0 ms 0 KB -