oj.uz

Submission #482226

# Submission time Handle Problem Language Result Execution time Memory
482226 2021-10-23T19:44:06 Z nonsensenonsense1 New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 35124 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 = 1;
int n, k, q, next[N], type_amt[N], ans[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;
	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);
			ut[a[j].t] = 1;
			inter.push_back(j);
		}
		for (int j = 0; j < n; ++j) active[j] = a[j].l <= qr[i].y && a[j].r > qr[until - 1].y && !ut[a[j].t];
		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);
			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:56:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   56 |   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:64:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    while (l == j || l <= n && amt < k - inter_type.size()) {
      |                               ~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:64:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   64 |    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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d%d%d", &a[i].x, &a[i].t, &a[i].l, &a[i].r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d%d", &qr[i].l, &qr[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7288 KB Output is correct
3 Correct 4 ms 7332 KB Output is correct
4 Correct 4 ms 7336 KB Output is correct
5 Correct 6 ms 7332 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 7 ms 7340 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7372 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 6 ms 7372 KB Output is correct
13 Correct 6 ms 7344 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 6 ms 7372 KB Output is correct
16 Correct 6 ms 7344 KB Output is correct
17 Correct 7 ms 7372 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 7 ms 7376 KB Output is correct
20 Correct 6 ms 7372 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 6 ms 7372 KB Output is correct
23 Correct 7 ms 7372 KB Output is correct
24 Correct 7 ms 7372 KB Output is correct
25 Correct 6 ms 7372 KB Output is correct
26 Correct 6 ms 7372 KB Output is correct
27 Correct 6 ms 7372 KB Output is correct
28 Correct 5 ms 7292 KB Output is correct
29 Correct 5 ms 7372 KB Output is correct
30 Correct 5 ms 7344 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 4 ms 7288 KB Output is correct
3 Correct 4 ms 7332 KB Output is correct
4 Correct 4 ms 7336 KB Output is correct
5 Correct 6 ms 7332 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 7 ms 7340 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7372 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 6 ms 7372 KB Output is correct
13 Correct 6 ms 7344 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 6 ms 7372 KB Output is correct
16 Correct 6 ms 7344 KB Output is correct
17 Correct 7 ms 7372 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 7 ms 7376 KB Output is correct
20 Correct 6 ms 7372 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 6 ms 7372 KB Output is correct
23 Correct 7 ms 7372 KB Output is correct
24 Correct 7 ms 7372 KB Output is correct
25 Correct 6 ms 7372 KB Output is correct
26 Correct 6 ms 7372 KB Output is correct
27 Correct 6 ms 7372 KB Output is correct
28 Correct 5 ms 7292 KB Output is correct
29 Correct 5 ms 7372 KB Output is correct
30 Correct 5 ms 7344 KB Output is correct
31 Execution timed out 5054 ms 12868 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 33112 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 7288 KB Output is correct
3 Correct 4 ms 7332 KB Output is correct
4 Correct 4 ms 7336 KB Output is correct
5 Correct 6 ms 7332 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 7 ms 7340 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7372 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 6 ms 7372 KB Output is correct
13 Correct 6 ms 7344 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 6 ms 7372 KB Output is correct
16 Correct 6 ms 7344 KB Output is correct
17 Correct 7 ms 7372 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 7 ms 7376 KB Output is correct
20 Correct 6 ms 7372 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 6 ms 7372 KB Output is correct
23 Correct 7 ms 7372 KB Output is correct
24 Correct 7 ms 7372 KB Output is correct
25 Correct 6 ms 7372 KB Output is correct
26 Correct 6 ms 7372 KB Output is correct
27 Correct 6 ms 7372 KB Output is correct
28 Correct 5 ms 7292 KB Output is correct
29 Correct 5 ms 7372 KB Output is correct
30 Correct 5 ms 7344 KB Output is correct
31 Execution timed out 5054 ms 12868 KB Time limit exceeded
32 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 7288 KB Output is correct
3 Correct 4 ms 7332 KB Output is correct
4 Correct 4 ms 7336 KB Output is correct
5 Correct 6 ms 7332 KB Output is correct
6 Correct 7 ms 7372 KB Output is correct
7 Correct 7 ms 7340 KB Output is correct
8 Correct 6 ms 7372 KB Output is correct
9 Correct 7 ms 7372 KB Output is correct
10 Correct 7 ms 7372 KB Output is correct
11 Correct 7 ms 7372 KB Output is correct
12 Correct 6 ms 7372 KB Output is correct
13 Correct 6 ms 7344 KB Output is correct
14 Correct 5 ms 7372 KB Output is correct
15 Correct 6 ms 7372 KB Output is correct
16 Correct 6 ms 7344 KB Output is correct
17 Correct 7 ms 7372 KB Output is correct
18 Correct 6 ms 7372 KB Output is correct
19 Correct 7 ms 7376 KB Output is correct
20 Correct 6 ms 7372 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 6 ms 7372 KB Output is correct
23 Correct 7 ms 7372 KB Output is correct
24 Correct 7 ms 7372 KB Output is correct
25 Correct 6 ms 7372 KB Output is correct
26 Correct 6 ms 7372 KB Output is correct
27 Correct 6 ms 7372 KB Output is correct
28 Correct 5 ms 7292 KB Output is correct
29 Correct 5 ms 7372 KB Output is correct
30 Correct 5 ms 7344 KB Output is correct
31 Execution timed out 5054 ms 12868 KB Time limit exceeded
32 Halted 0 ms 0 KB -