oj.uz

Submission #1074188

# Submission time Handle Problem Language Result Execution time Memory
1074188 2024-08-25T08:41:26 Z Joshua_Andersson Teams (IOI15_teams) C++14
0 / 100
 4000 ms 20352 KB 
#include "teams.h"

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll linf = ll(1e18);

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)

#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif

int n;
vi a;
vi b;
typedef pair<double, int> pt;
vector<p2> pts;

void init(int N, int A[], int B[])
{
	n = N;
	a.resize(N);
	b.resize(N);
	rep(i, N) a[i] = A[i], b[i] = B[i];

	rep(i, n)
	{
		pts.emplace_back(b[i], a[i]);
	}
	sort(all(pts));
}

int rectangle_sum(int xlo, int xhi, int ylo, int yhi)
{
	int ret = 0;

	repp(i, ylo, yhi+1)
	{
		ret += pts[i].second >= xlo && pts[i].second <= xhi;
	}

	return ret;
}

int can(int m, int K[]) {
	//cout << rectangle_sum(1, 3, 1, 3);
	vi k(m);
	rep(i, m) k[i] = K[i];

	sort(all(k));

	int lo = 0;
	rep(i, m)
	{
		while (lo < sz(pts) && pts[lo].first < k[i])
		{
			lo++;
		}
		if (rectangle_sum(0, k[i], lo, n-1)<k[i])
		{
			return 0;
		}
		int lob = lo-1;
		int hib = n;
		while (lob+1<hib)
		{
			int mid = (lob + hib) / 2;
			if (rectangle_sum(0, k[i], lo, mid) < k[i])
			{
				lob = mid;
			}
			else hib = mid;
		}
		lo = hib+1;
	}

	return 1;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 1 ms 344 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4284 KB Output is correct
2 Correct 16 ms 4308 KB Output is correct
3 Correct 16 ms 4260 KB Output is correct
4 Correct 15 ms 4876 KB Output is correct
5 Correct 50 ms 3792 KB Output is correct
6 Correct 37 ms 3796 KB Output is correct
7 Correct 10 ms 3796 KB Output is correct
8 Correct 12 ms 3796 KB Output is correct
9 Correct 2242 ms 3796 KB Output is correct
10 Correct 1599 ms 3536 KB Output is correct
11 Correct 188 ms 3540 KB Output is correct
12 Correct 30 ms 3776 KB Output is correct
13 Correct 14 ms 4048 KB Output is correct
14 Correct 12 ms 4052 KB Output is correct
15 Incorrect 13 ms 4052 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 4564 KB Output is correct
2 Correct 155 ms 4560 KB Output is correct
3 Execution timed out 4067 ms 4564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1741 ms 20224 KB Output is correct
2 Correct 1695 ms 20352 KB Output is correct
3 Execution timed out 4042 ms 19160 KB Time limit exceeded
4 Halted 0 ms 0 KB -