Submission #387601

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
387601	2021-04-09T03:31:24 Z	milleniumEeee	New Home (APIO18_new_home)	C++17	5 / 100	5000 ms	16144 KB

new_home

#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
using namespace std;

const int MAXN = (int)1e8 + 8;
const int INF = 1e9;

int x[MAXN];
int t[MAXN];
int a[MAXN];
int b[MAXN];
int n, k, q;

int get(int pos, int tiktak) {
	set <int> st;
	for (int i = 1; i <= n; i++) {
		if (a[i] <= tiktak && tiktak <= b[i]) {
			st.insert(t[i]);
		}
	}
	if (szof(st) != k) {
		return -1;
	}
	int mx = 0;
	for (int type : st) {
		int mn = INF;
		for (int i = 1; i <= n; i++) {
			if (a[i] <= tiktak && tiktak <= b[i] && t[i] == type) {
				mn = min(mn, abs(pos - x[i]));
			}
		}
		mx = max(mx, mn);
	}
	return mx;
}

signed main() {
	fastInp;
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> t[i] >> a[i] >> b[i];
	}
	while (q--) {
		int pos, tiktak;
		cin >> pos >> tiktak;
		cout << get(pos, tiktak) << endl;
	}
}

/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	9 ms	332 KB	Output is correct
6	Correct	11 ms	332 KB	Output is correct
7	Correct	7 ms	344 KB	Output is correct
8	Correct	10 ms	332 KB	Output is correct
9	Correct	11 ms	340 KB	Output is correct
10	Correct	12 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	53 ms	332 KB	Output is correct
16	Correct	78 ms	332 KB	Output is correct
17	Correct	22 ms	332 KB	Output is correct
18	Correct	44 ms	332 KB	Output is correct
19	Correct	64 ms	332 KB	Output is correct
20	Correct	22 ms	344 KB	Output is correct
21	Correct	117 ms	332 KB	Output is correct
22	Correct	45 ms	332 KB	Output is correct
23	Correct	47 ms	332 KB	Output is correct
24	Correct	52 ms	332 KB	Output is correct
25	Correct	20 ms	332 KB	Output is correct
26	Correct	3 ms	332 KB	Output is correct
27	Correct	14 ms	332 KB	Output is correct
28	Correct	4 ms	332 KB	Output is correct
29	Correct	3 ms	296 KB	Output is correct
30	Correct	2 ms	332 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	9 ms	332 KB	Output is correct
6	Correct	11 ms	332 KB	Output is correct
7	Correct	7 ms	344 KB	Output is correct
8	Correct	10 ms	332 KB	Output is correct
9	Correct	11 ms	340 KB	Output is correct
10	Correct	12 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	53 ms	332 KB	Output is correct
16	Correct	78 ms	332 KB	Output is correct
17	Correct	22 ms	332 KB	Output is correct
18	Correct	44 ms	332 KB	Output is correct
19	Correct	64 ms	332 KB	Output is correct
20	Correct	22 ms	344 KB	Output is correct
21	Correct	117 ms	332 KB	Output is correct
22	Correct	45 ms	332 KB	Output is correct
23	Correct	47 ms	332 KB	Output is correct
24	Correct	52 ms	332 KB	Output is correct
25	Correct	20 ms	332 KB	Output is correct
26	Correct	3 ms	332 KB	Output is correct
27	Correct	14 ms	332 KB	Output is correct
28	Correct	4 ms	332 KB	Output is correct
29	Correct	3 ms	296 KB	Output is correct
30	Correct	2 ms	332 KB	Output is correct
31	Execution timed out	5040 ms	3336 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	5046 ms	16144 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	5061 ms	12880 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	9 ms	332 KB	Output is correct
6	Correct	11 ms	332 KB	Output is correct
7	Correct	7 ms	344 KB	Output is correct
8	Correct	10 ms	332 KB	Output is correct
9	Correct	11 ms	340 KB	Output is correct
10	Correct	12 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	53 ms	332 KB	Output is correct
16	Correct	78 ms	332 KB	Output is correct
17	Correct	22 ms	332 KB	Output is correct
18	Correct	44 ms	332 KB	Output is correct
19	Correct	64 ms	332 KB	Output is correct
20	Correct	22 ms	344 KB	Output is correct
21	Correct	117 ms	332 KB	Output is correct
22	Correct	45 ms	332 KB	Output is correct
23	Correct	47 ms	332 KB	Output is correct
24	Correct	52 ms	332 KB	Output is correct
25	Correct	20 ms	332 KB	Output is correct
26	Correct	3 ms	332 KB	Output is correct
27	Correct	14 ms	332 KB	Output is correct
28	Correct	4 ms	332 KB	Output is correct
29	Correct	3 ms	296 KB	Output is correct
30	Correct	2 ms	332 KB	Output is correct
31	Execution timed out	5040 ms	3336 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	9 ms	332 KB	Output is correct
6	Correct	11 ms	332 KB	Output is correct
7	Correct	7 ms	344 KB	Output is correct
8	Correct	10 ms	332 KB	Output is correct
9	Correct	11 ms	340 KB	Output is correct
10	Correct	12 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	3 ms	332 KB	Output is correct
13	Correct	2 ms	332 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	53 ms	332 KB	Output is correct
16	Correct	78 ms	332 KB	Output is correct
17	Correct	22 ms	332 KB	Output is correct
18	Correct	44 ms	332 KB	Output is correct
19	Correct	64 ms	332 KB	Output is correct
20	Correct	22 ms	344 KB	Output is correct
21	Correct	117 ms	332 KB	Output is correct
22	Correct	45 ms	332 KB	Output is correct
23	Correct	47 ms	332 KB	Output is correct
24	Correct	52 ms	332 KB	Output is correct
25	Correct	20 ms	332 KB	Output is correct
26	Correct	3 ms	332 KB	Output is correct
27	Correct	14 ms	332 KB	Output is correct
28	Correct	4 ms	332 KB	Output is correct
29	Correct	3 ms	296 KB	Output is correct
30	Correct	2 ms	332 KB	Output is correct
31	Execution timed out	5040 ms	3336 KB	Time limit exceeded
32	Halted	0 ms	0 KB	-

Submission #387601

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 7.0

Subtask #3 0 / 10.0

Subtask #4 0 / 23.0

Subtask #5 0 / 35.0

Subtask #6 0 / 20.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 7.0

Subtask #3
0 / 10.0

Subtask #4
0 / 23.0

Subtask #5
0 / 35.0

Subtask #6
0 / 20.0