oj.uz

Submission #482227

# Submission time Handle Problem Language Result Execution time Memory
482227 2021-10-23T20:09:03 Z nonsensenonsense1 New Home (APIO18_new_home) C++17
10 / 100
 5000 ms 47996 KB 
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cstring>
#include <vector>

const int INF = 0x3f3f3f3f;

struct store {
	int x, t, l, r;
	bool operator<(store arg) {
		return x < arg.x;
	}
};

struct query {
	int l, y, ind;
	bool operator<(query arg) {
		return y < arg.y;
	}
};

bool cmp_l(query a, query b) 
{
	return a.l < b.l;
}

const int N = 300000;
const int K = 600;
int n, k, q, next[N + 1], type_amt[N], ans[N], it[N], fi[N], last[N], to[N];
bool ut[N], active[N];
store a[N + 1];
query qr[N];
std::vector<int> tp[N];

int main() 
{
	scanf("%d%d%d", &n, &k, &q);
	a[n].x = INF;
	next[n] = n;
	memset(to, 0x3f, k << 2);
	for (int i = 0; i < n; ++i) {
		scanf("%d%d%d%d", &a[i].x, &a[i].t, &a[i].l, &a[i].r);
		--a[i].t;
		++a[i].r;
	}
	std::sort(a, a + n);
	for (int i = 0; i < q; ++i) {
		scanf("%d%d", &qr[i].l, &qr[i].y);
		qr[i].ind = i;
	}
	std::sort(qr, qr + q);
	for (int i = 0; i < n; ++i) tp[a[i].t].push_back(i);
	for (int i = 0; i < q;) {
		memset(ut, 0, k);
		int until = std::min(i + K, q);
		std::vector<int> inter, inter_type;
		for (int j = 0; j < n; ++j) if (a[j].l >= qr[i].y + 1 && a[j].l <= qr[until - 1].y || a[j].r >= qr[i].y + 1 && a[j].r <= qr[until - 1].y) {
			if (!ut[a[j].t]) {
				inter_type.push_back(a[j].t);
				fi[a[j].t] = n;
			}
			ut[a[j].t] = 1;
			inter.push_back(j);
		}
		memset(last, -1, n << 2);
		for (int j = 0; j < n; ++j) if (active[j] = a[j].l <= qr[i].y && a[j].r > qr[until - 1].y) {
			if (ut[a[j].t]) {
				if (last[a[j].t] == -1) fi[a[j].t] = j;
				else next[last[a[j].t]] = j;
				last[a[j].t] = j;
				next[j] = n;
			}
			else active[j] = true;
		}
		memset(type_amt, 0, k << 2);
		for (int j = 0, l = 0, amt = 0; j < n; ++j) {
			while (l == j || l <= n && amt < k - inter_type.size()) {
				if (l < n && active[l]) {
					if (!type_amt[a[l].t]) ++amt;
					++type_amt[a[l].t];
				}
				++l;
			}
			next[j] = l;
			if (active[j]) {
				--type_amt[a[j].t];
				if (!type_amt[a[j].t]) --amt;
			}
		}
		std::sort(qr + i, qr + until, cmp_l);
		for (int j = 0; i < until; ++i) {
			while (qr[i].l - a[j].x > a[next[j] - 1].x - qr[i].l) ++j;
			int res = std::min(j ? qr[i].l - a[j - 1].x : INF, a[next[j] - 1].x - qr[i].l);
			for (int k = 0; k < (int)inter.size(); ++k) if (a[inter[k]].l <= qr[i].y && a[inter[k]].r > qr[i].y) to[a[inter[k]].t] = std::min(to[a[inter[k]].t], abs(qr[i].l - a[inter[k]].x));
			for (int k = 0; k < (int)inter_type.size(); ++k) {
				while (a[next[fi[inter_type[k]]]].x <= qr[i].l) fi[inter_type[k]] = next[fi[inter_type[k]]];
				res = std::max(res, std::min(to[inter_type[k]], std::min(fi[inter_type[k]] == n ? INF : qr[i].l - a[fi[inter_type[k]]].x, a[next[fi[inter_type[k]]]].x - qr[i].l)));
				to[inter_type[k]] = INF;
			}
			ans[qr[i].ind] = res > INF / 2 ? -1 : res;
		}
	}
	for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:58:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   58 |   for (int j = 0; j < n; ++j) if (a[j].l >= qr[i].y + 1 && a[j].l <= qr[until - 1].y || a[j].r >= qr[i].y + 1 && a[j].r <= qr[until - 1].y) {
      |                                   ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:67:45: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   67 |   for (int j = 0; j < n; ++j) if (active[j] = a[j].l <= qr[i].y && a[j].r > qr[until - 1].y) {
      |                                   ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:78:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    while (l == j || l <= n && amt < k - inter_type.size()) {
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:78:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |    while (l == j || l <= n && amt < k - inter_type.size()) {
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d%d", &n, &k, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d%d%d", &a[i].x, &a[i].t, &a[i].l, &a[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &qr[i].l, &qr[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1877 ms 25560 KB Output is correct
2 Correct 2259 ms 34792 KB Output is correct
3 Correct 2281 ms 47960 KB Output is correct
4 Correct 2036 ms 40112 KB Output is correct
5 Correct 1958 ms 34324 KB Output is correct
6 Correct 2540 ms 34636 KB Output is correct
7 Correct 2396 ms 47996 KB Output is correct
8 Correct 1920 ms 39752 KB Output is correct
9 Correct 1929 ms 38248 KB Output is correct
10 Correct 2069 ms 36420 KB Output is correct
11 Correct 1903 ms 34856 KB Output is correct
12 Correct 1937 ms 36336 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5101 ms 21172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

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