oj.uz

Submission #405490

# Submission time Handle Problem Language Result Execution time Memory
405490 2021-05-16T13:08:49 Z saleh New Home (APIO18_new_home) C++17
12 / 100
 5000 ms 59652 KB 
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,")

#include <bits/stdc++.h>


using namespace std;


const int MAXN = 60 * 1000 + 23, MAXK = MAXN;






/*
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
*/









int n, q, k, x[MAXN], t[MAXN], a[MAXN], b[MAXN], l[MAXN], y[MAXN], ans[MAXN];
vector<int> cy;
map<int, vector<int>> add, rem, qu;
map<int, map<int, int>> cnt;
set<int> s[MAXK];



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> k >> q;
	if (n >= MAXN || q >= MAXN || k >= MAXK) return 0;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> t[i] >> a[i] >> b[i];
		cy.push_back(a[i]), cy.push_back(b[i]);
		add[a[i]].push_back(i), rem[b[i]].push_back(i);
	}
	for (int i = 0; i < q; i++) {
		cin >> l[i] >> y[i];
		cy.push_back(y[i]);
		qu[y[i]].push_back(i);
	}
	sort(cy.begin(), cy.end());
	cy.resize(unique(cy.begin(), cy.end()) - cy.begin());
	for (auto i : cy) {
		for (auto j : add[i]) if (cnt[t[j]][x[j]]++ == 0) s[t[j]].insert(x[j]);
		for (auto j : qu[i]) {
			ans[j] = -1;
			for (int chi = 1; chi <= k; chi++) {
				int jav = INT_MAX;
				auto tmp = s[chi].upper_bound(l[j]);
				if (tmp != s[chi].end()) jav = *tmp - l[j];
				if (tmp != s[chi].begin()) {
					tmp--;
					jav = min(jav, l[j] - *tmp);
				}
				ans[j] = max(ans[j], jav);
			}
		}
		for (auto j : rem[i]) if (--cnt[t[j]][x[j]] == 0) s[t[j]].erase(x[j]);
	}
	for (int i = 0; i < q; i++) cout << (ans[i] == INT_MAX? -1: ans[i]) << '\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 4 ms 3532 KB Output is correct
7 Correct 5 ms 3532 KB Output is correct
8 Correct 5 ms 3532 KB Output is correct
9 Correct 5 ms 3532 KB Output is correct
10 Correct 4 ms 3532 KB Output is correct
11 Correct 4 ms 3404 KB Output is correct
12 Correct 4 ms 3532 KB Output is correct
13 Correct 4 ms 3404 KB Output is correct
14 Correct 4 ms 3404 KB Output is correct
15 Correct 5 ms 3532 KB Output is correct
16 Correct 5 ms 3532 KB Output is correct
17 Correct 4 ms 3532 KB Output is correct
18 Correct 6 ms 3532 KB Output is correct
19 Correct 5 ms 3532 KB Output is correct
20 Correct 4 ms 3532 KB Output is correct
21 Correct 3 ms 3268 KB Output is correct
22 Correct 5 ms 3532 KB Output is correct
23 Correct 5 ms 3532 KB Output is correct
24 Correct 5 ms 3532 KB Output is correct
25 Correct 4 ms 3532 KB Output is correct
26 Correct 6 ms 3524 KB Output is correct
27 Correct 3 ms 3148 KB Output is correct
28 Correct 5 ms 3404 KB Output is correct
29 Correct 4 ms 3404 KB Output is correct
30 Correct 3 ms 3404 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 4 ms 3532 KB Output is correct
7 Correct 5 ms 3532 KB Output is correct
8 Correct 5 ms 3532 KB Output is correct
9 Correct 5 ms 3532 KB Output is correct
10 Correct 4 ms 3532 KB Output is correct
11 Correct 4 ms 3404 KB Output is correct
12 Correct 4 ms 3532 KB Output is correct
13 Correct 4 ms 3404 KB Output is correct
14 Correct 4 ms 3404 KB Output is correct
15 Correct 5 ms 3532 KB Output is correct
16 Correct 5 ms 3532 KB Output is correct
17 Correct 4 ms 3532 KB Output is correct
18 Correct 6 ms 3532 KB Output is correct
19 Correct 5 ms 3532 KB Output is correct
20 Correct 4 ms 3532 KB Output is correct
21 Correct 3 ms 3268 KB Output is correct
22 Correct 5 ms 3532 KB Output is correct
23 Correct 5 ms 3532 KB Output is correct
24 Correct 5 ms 3532 KB Output is correct
25 Correct 4 ms 3532 KB Output is correct
26 Correct 6 ms 3524 KB Output is correct
27 Correct 3 ms 3148 KB Output is correct
28 Correct 5 ms 3404 KB Output is correct
29 Correct 4 ms 3404 KB Output is correct
30 Correct 3 ms 3404 KB Output is correct
31 Correct 4480 ms 59416 KB Output is correct
32 Correct 69 ms 6440 KB Output is correct
33 Correct 703 ms 56876 KB Output is correct
34 Correct 3363 ms 57044 KB Output is correct
35 Correct 2169 ms 59652 KB Output is correct
36 Correct 713 ms 59328 KB Output is correct
37 Correct 571 ms 56644 KB Output is correct
38 Correct 445 ms 56516 KB Output is correct
39 Correct 366 ms 56436 KB Output is correct
40 Correct 378 ms 56432 KB Output is correct
41 Correct 706 ms 56632 KB Output is correct
42 Correct 795 ms 56456 KB Output is correct
43 Correct 129 ms 7064 KB Output is correct
44 Correct 641 ms 56676 KB Output is correct
45 Correct 515 ms 56624 KB Output is correct
46 Correct 386 ms 56824 KB Output is correct
47 Correct 298 ms 54812 KB Output is correct
48 Correct 285 ms 54452 KB Output is correct
49 Correct 332 ms 55472 KB Output is correct
50 Correct 555 ms 56216 KB Output is correct
51 Correct 325 ms 55236 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 4 ms 3532 KB Output is correct
7 Correct 5 ms 3532 KB Output is correct
8 Correct 5 ms 3532 KB Output is correct
9 Correct 5 ms 3532 KB Output is correct
10 Correct 4 ms 3532 KB Output is correct
11 Correct 4 ms 3404 KB Output is correct
12 Correct 4 ms 3532 KB Output is correct
13 Correct 4 ms 3404 KB Output is correct
14 Correct 4 ms 3404 KB Output is correct
15 Correct 5 ms 3532 KB Output is correct
16 Correct 5 ms 3532 KB Output is correct
17 Correct 4 ms 3532 KB Output is correct
18 Correct 6 ms 3532 KB Output is correct
19 Correct 5 ms 3532 KB Output is correct
20 Correct 4 ms 3532 KB Output is correct
21 Correct 3 ms 3268 KB Output is correct
22 Correct 5 ms 3532 KB Output is correct
23 Correct 5 ms 3532 KB Output is correct
24 Correct 5 ms 3532 KB Output is correct
25 Correct 4 ms 3532 KB Output is correct
26 Correct 6 ms 3524 KB Output is correct
27 Correct 3 ms 3148 KB Output is correct
28 Correct 5 ms 3404 KB Output is correct
29 Correct 4 ms 3404 KB Output is correct
30 Correct 3 ms 3404 KB Output is correct
31 Correct 4480 ms 59416 KB Output is correct
32 Correct 69 ms 6440 KB Output is correct
33 Correct 703 ms 56876 KB Output is correct
34 Correct 3363 ms 57044 KB Output is correct
35 Correct 2169 ms 59652 KB Output is correct
36 Correct 713 ms 59328 KB Output is correct
37 Correct 571 ms 56644 KB Output is correct
38 Correct 445 ms 56516 KB Output is correct
39 Correct 366 ms 56436 KB Output is correct
40 Correct 378 ms 56432 KB Output is correct
41 Correct 706 ms 56632 KB Output is correct
42 Correct 795 ms 56456 KB Output is correct
43 Correct 129 ms 7064 KB Output is correct
44 Correct 641 ms 56676 KB Output is correct
45 Correct 515 ms 56624 KB Output is correct
46 Correct 386 ms 56824 KB Output is correct
47 Correct 298 ms 54812 KB Output is correct
48 Correct 285 ms 54452 KB Output is correct
49 Correct 332 ms 55472 KB Output is correct
50 Correct 555 ms 56216 KB Output is correct
51 Correct 325 ms 55236 KB Output is correct
52 Execution timed out 5046 ms 33272 KB Time limit exceeded
53 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB Output is correct
2 Correct 2 ms 3148 KB Output is correct
3 Correct 3 ms 3148 KB Output is correct
4 Correct 2 ms 3148 KB Output is correct
5 Correct 3 ms 3148 KB Output is correct
6 Correct 4 ms 3532 KB Output is correct
7 Correct 5 ms 3532 KB Output is correct
8 Correct 5 ms 3532 KB Output is correct
9 Correct 5 ms 3532 KB Output is correct
10 Correct 4 ms 3532 KB Output is correct
11 Correct 4 ms 3404 KB Output is correct
12 Correct 4 ms 3532 KB Output is correct
13 Correct 4 ms 3404 KB Output is correct
14 Correct 4 ms 3404 KB Output is correct
15 Correct 5 ms 3532 KB Output is correct
16 Correct 5 ms 3532 KB Output is correct
17 Correct 4 ms 3532 KB Output is correct
18 Correct 6 ms 3532 KB Output is correct
19 Correct 5 ms 3532 KB Output is correct
20 Correct 4 ms 3532 KB Output is correct
21 Correct 3 ms 3268 KB Output is correct
22 Correct 5 ms 3532 KB Output is correct
23 Correct 5 ms 3532 KB Output is correct
24 Correct 5 ms 3532 KB Output is correct
25 Correct 4 ms 3532 KB Output is correct
26 Correct 6 ms 3524 KB Output is correct
27 Correct 3 ms 3148 KB Output is correct
28 Correct 5 ms 3404 KB Output is correct
29 Correct 4 ms 3404 KB Output is correct
30 Correct 3 ms 3404 KB Output is correct
31 Correct 4480 ms 59416 KB Output is correct
32 Correct 69 ms 6440 KB Output is correct
33 Correct 703 ms 56876 KB Output is correct
34 Correct 3363 ms 57044 KB Output is correct
35 Correct 2169 ms 59652 KB Output is correct
36 Correct 713 ms 59328 KB Output is correct
37 Correct 571 ms 56644 KB Output is correct
38 Correct 445 ms 56516 KB Output is correct
39 Correct 366 ms 56436 KB Output is correct
40 Correct 378 ms 56432 KB Output is correct
41 Correct 706 ms 56632 KB Output is correct
42 Correct 795 ms 56456 KB Output is correct
43 Correct 129 ms 7064 KB Output is correct
44 Correct 641 ms 56676 KB Output is correct
45 Correct 515 ms 56624 KB Output is correct
46 Correct 386 ms 56824 KB Output is correct
47 Correct 298 ms 54812 KB Output is correct
48 Correct 285 ms 54452 KB Output is correct
49 Correct 332 ms 55472 KB Output is correct
50 Correct 555 ms 56216 KB Output is correct
51 Correct 325 ms 55236 KB Output is correct
52 Incorrect 2 ms 3020 KB Output isn't correct
53 Halted 0 ms 0 KB -