oj.uz

Submission #1074168

# Submission time Handle Problem Language Result Execution time Memory
1074168 2024-08-25T08:32:53 Z Joshua_Andersson Teams (IOI15_teams) C++14
0 / 100
 4000 ms 21216 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;
}

const double inf = 2e9;
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;
		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 = lob+1;
	}

	return 1;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4308 KB Output is correct
2 Correct 17 ms 4308 KB Output is correct
3 Correct 13 ms 4320 KB Output is correct
4 Correct 17 ms 4812 KB Output is correct
5 Correct 51 ms 3796 KB Output is correct
6 Correct 31 ms 3892 KB Output is correct
7 Correct 11 ms 3792 KB Output is correct
8 Correct 11 ms 3796 KB Output is correct
9 Correct 3152 ms 3904 KB Output is correct
10 Correct 1963 ms 3540 KB Output is correct
11 Correct 210 ms 3540 KB Output is correct
12 Correct 23 ms 3796 KB Output is correct
13 Correct 16 ms 3880 KB Output is correct
14 Correct 12 ms 4064 KB Output is correct
15 Incorrect 16 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 146 ms 4560 KB Output is correct
2 Correct 238 ms 4556 KB Output is correct
3 Execution timed out 4088 ms 4324 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1587 ms 20240 KB Output is correct
2 Correct 1556 ms 20432 KB Output is correct
3 Execution timed out 4067 ms 21216 KB Time limit exceeded
4 Halted 0 ms 0 KB -