oj.uz

Submission #201912

# Submission time Handle Problem Language Result Execution time Memory
201912 2020-02-12T19:28:45 Z maruii New Home (APIO18_new_home) C++14
80 / 100
 5000 ms 100356 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

const int SIZE = 1 << 20;
struct ST {
	int A[2 * SIZE];
	void init() { fill(A, A + 2 * SIZE, -1e9); }
	void update(int x, int v) {
		x += SIZE; A[x] = v;
		for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
	}
	int query(int s, int e) {
		int ret = -1e9;
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) ret = max(ret, A[s++]);
			if (~e & 1) ret = max(ret, A[e--]);
		}
		return ret;
	}
} seg;

int N, K, Q;
vector<pair<int, pii> > qin, qout, qry;
vector<pii> xx;
int ans[300005];
multiset<int> MS[300005];

void solve() {
	xx.clear();
	seg.init();
	int j = 0, k = 0;
	for (auto i : qry) {
		while (j < qin.size() && qin[j].ff <= i.ff) {
			int x = qin[j].ss.ff, c = qin[j].ss.ss;
			++j;
			auto it = MS[c].lower_bound(x);
			if (*it != x) {
				xx.emplace_back((*it + x) / 2, c);
				--it;
				xx.emplace_back((x + *it) / 2, c);
			}
			MS[c].insert(x);
		}
		while (k < qout.size() && qout[k].ff < i.ff) {
			int x = qout[k].ss.ff, c = qout[k].ss.ss;
			MS[c].erase(MS[c].find(x));
			++k;
			auto it = MS[c].lower_bound(x);
			if (*it != x) {
				auto jt = it;
				--jt;
				xx.emplace_back((*it + *jt) / 2, c);
			}
		}
	}
	while (j < qin.size()) {
		int x = qin[j].ss.ff, c = qin[j].ss.ss;
		MS[c].insert(x);
		++j;
	}
	while (k < qout.size()) {
		int x = qout[k].ss.ff, c = qout[k].ss.ss;
		MS[c].erase(MS[c].find(x));
		++k;
	}
	sort(xx.begin(), xx.end());
	j = k = 0;
	int cnt = 0;
	for (auto i : qry) {
		while (j < qin.size() && qin[j].ff <= i.ff) {
			int x = qin[j].ss.ff, c = qin[j].ss.ss, t, p, q;
			auto it = MS[c].lower_bound(x);
			if (MS[c].size() == 2) ++cnt;
			if (*it != x) {
				auto jt = it;
				--jt;
				t = lower_bound(xx.begin(), xx.end(), pii((*it + *jt) / 2, c)) - xx.begin();
				p = lower_bound(xx.begin(), xx.end(), pii((*it + x) / 2, c)) - xx.begin();
				q = lower_bound(xx.begin(), xx.end(), pii((x + *jt) / 2, c)) - xx.begin();
				if (MS[c].size() > 2) seg.update(t, -1e9);
				seg.update(p, *it);
				seg.update(q, x);
			}
			MS[c].insert(x);
			++j;
		}
		while (k < qout.size() && qout[k].ff < i.ff) {
			int x = qout[k].ss.ff, c = qout[k].ss.ss, t, p, q;
			MS[c].erase(MS[c].find(x));
			++k;
			auto it = MS[c].lower_bound(x);
			if (*it != x) {
				auto jt = it;
				--jt;
				t = lower_bound(xx.begin(), xx.end(), pii((*it + *jt) / 2, c)) - xx.begin();
				p = lower_bound(xx.begin(), xx.end(), pii((*it + x) / 2, c)) - xx.begin();
				q = lower_bound(xx.begin(), xx.end(), pii((x + *jt) / 2, c)) - xx.begin();
				if (MS[c].size() > 2) seg.update(t, *it);
				seg.update(p, -1e9);
				seg.update(q, -1e9);
			}
			if (MS[c].size() == 2) --cnt;
		}
		if (cnt == K) ans[i.ss.ss] = max(ans[i.ss.ss], (seg.query(0, lower_bound(xx.begin(), xx.end(), pii(i.ss.ff + 1, 0)) - xx.begin() - 1) - i.ss.ff) / 2);
	}
	while (j < qin.size()) {
		int x = qin[j].ss.ff, c = qin[j].ss.ss;
		MS[c].insert(x);
		++j;
	}
	while (k < qout.size()) {
		int x = qout[k].ss.ff, c = qout[k].ss.ss;
		MS[c].erase(MS[c].find(x));
		++k;
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K >> Q;
	fill(ans, ans + Q, -1);
	for (int i = 1; i <= K; ++i) {
		MS[i].insert(1e9);
		MS[i].insert(-1e9);
	}
	for (int i = 0; i < N; ++i) {
		int a, b, c, d; cin >> a >> b >> c >> d;
		a *= 2;
		qin.emplace_back(c, pii(a, b));
		qout.emplace_back(d, pii(a, b));
	}
	for (int i = 0; i < Q; ++i) {
		int a, b; cin >> a >> b;
		a *= 2;
		qry.emplace_back(b, pii(a, i));
	}
	sort(qin.begin(), qin.end());
	sort(qout.begin(), qout.end());
	sort(qry.begin(), qry.end());
	solve();
	for (auto &i : qin) i.ss.ff = -i.ss.ff;
	for (auto &i : qout) i.ss.ff = -i.ss.ff;
	for (auto &i : qry) i.ss.ff = -i.ss.ff;
	solve();
	for (int i = 0; i < Q; ++i) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

new_home.cpp: In function 'void solve()':
new_home.cpp:36:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:47:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:59:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:64:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~
new_home.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (j < qin.size() && qin[j].ff <= i.ff) {
          ~~^~~~~~~~~~~~
new_home.cpp:90:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (k < qout.size() && qout[k].ff < i.ff) {
          ~~^~~~~~~~~~~~~
new_home.cpp:109:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (j < qin.size()) {
         ~~^~~~~~~~~~~~
new_home.cpp:114:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (k < qout.size()) {
         ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 22 ms 22648 KB Output is correct
4 Correct 20 ms 22648 KB Output is correct
5 Correct 20 ms 22520 KB Output is correct
6 Correct 21 ms 22648 KB Output is correct
7 Correct 21 ms 22776 KB Output is correct
8 Correct 21 ms 22776 KB Output is correct
9 Correct 22 ms 22776 KB Output is correct
10 Correct 21 ms 22648 KB Output is correct
11 Correct 20 ms 22648 KB Output is correct
12 Correct 21 ms 22520 KB Output is correct
13 Correct 20 ms 22648 KB Output is correct
14 Correct 21 ms 22776 KB Output is correct
15 Correct 21 ms 22648 KB Output is correct
16 Correct 22 ms 22776 KB Output is correct
17 Correct 21 ms 22648 KB Output is correct
18 Correct 20 ms 22776 KB Output is correct
19 Correct 21 ms 22776 KB Output is correct
20 Correct 22 ms 22648 KB Output is correct
21 Correct 21 ms 22776 KB Output is correct
22 Correct 22 ms 22776 KB Output is correct
23 Correct 21 ms 22780 KB Output is correct
24 Correct 24 ms 22776 KB Output is correct
25 Correct 21 ms 22648 KB Output is correct
26 Correct 22 ms 22648 KB Output is correct
27 Correct 22 ms 22648 KB Output is correct
28 Correct 22 ms 22648 KB Output is correct
29 Correct 21 ms 22648 KB Output is correct
30 Correct 21 ms 22648 KB Output is correct
31 Correct 529 ms 32800 KB Output is correct
32 Correct 138 ms 27564 KB Output is correct
33 Correct 507 ms 30888 KB Output is correct
34 Correct 457 ms 31140 KB Output is correct
35 Correct 551 ms 32808 KB Output is correct
36 Correct 553 ms 32676 KB Output is correct
37 Correct 396 ms 30504 KB Output is correct
38 Correct 408 ms 30496 KB Output is correct
39 Correct 342 ms 30376 KB Output is correct
40 Correct 351 ms 30372 KB Output is correct
41 Correct 371 ms 30500 KB Output is correct
42 Correct 369 ms 30628 KB Output is correct
43 Correct 110 ms 30756 KB Output is correct
44 Correct 378 ms 30496 KB Output is correct
45 Correct 370 ms 30492 KB Output is correct
46 Correct 359 ms 30372 KB Output is correct
47 Correct 238 ms 30244 KB Output is correct
48 Correct 250 ms 30240 KB Output is correct
49 Correct 280 ms 30372 KB Output is correct
50 Correct 284 ms 30496 KB Output is correct
51 Correct 283 ms 30244 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2096 ms 61892 KB Output is correct
2 Correct 1195 ms 55444 KB Output is correct
3 Correct 1317 ms 84460 KB Output is correct
4 Correct 2031 ms 65784 KB Output is correct
5 Correct 1193 ms 55280 KB Output is correct
6 Correct 1154 ms 55280 KB Output is correct
7 Correct 1317 ms 84460 KB Output is correct
8 Correct 2017 ms 65948 KB Output is correct
9 Correct 2021 ms 59120 KB Output is correct
10 Correct 1466 ms 55720 KB Output is correct
11 Correct 1095 ms 55452 KB Output is correct
12 Correct 1280 ms 55720 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3963 ms 58856 KB Output is correct
2 Correct 566 ms 53372 KB Output is correct
3 Correct 3636 ms 69736 KB Output is correct
4 Correct 2727 ms 98280 KB Output is correct
5 Correct 3336 ms 75368 KB Output is correct
6 Correct 3348 ms 79224 KB Output is correct
7 Correct 3468 ms 68952 KB Output is correct
8 Correct 3519 ms 69412 KB Output is correct
9 Correct 2896 ms 99540 KB Output is correct
10 Correct 3636 ms 78248 KB Output is correct
11 Correct 3990 ms 72808 KB Output is correct
12 Correct 3992 ms 70504 KB Output is correct
13 Correct 1559 ms 68380 KB Output is correct
14 Correct 1491 ms 67580 KB Output is correct
15 Correct 1756 ms 68836 KB Output is correct
16 Correct 1980 ms 70108 KB Output is correct
17 Correct 1826 ms 68720 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 22 ms 22648 KB Output is correct
4 Correct 20 ms 22648 KB Output is correct
5 Correct 20 ms 22520 KB Output is correct
6 Correct 21 ms 22648 KB Output is correct
7 Correct 21 ms 22776 KB Output is correct
8 Correct 21 ms 22776 KB Output is correct
9 Correct 22 ms 22776 KB Output is correct
10 Correct 21 ms 22648 KB Output is correct
11 Correct 20 ms 22648 KB Output is correct
12 Correct 21 ms 22520 KB Output is correct
13 Correct 20 ms 22648 KB Output is correct
14 Correct 21 ms 22776 KB Output is correct
15 Correct 21 ms 22648 KB Output is correct
16 Correct 22 ms 22776 KB Output is correct
17 Correct 21 ms 22648 KB Output is correct
18 Correct 20 ms 22776 KB Output is correct
19 Correct 21 ms 22776 KB Output is correct
20 Correct 22 ms 22648 KB Output is correct
21 Correct 21 ms 22776 KB Output is correct
22 Correct 22 ms 22776 KB Output is correct
23 Correct 21 ms 22780 KB Output is correct
24 Correct 24 ms 22776 KB Output is correct
25 Correct 21 ms 22648 KB Output is correct
26 Correct 22 ms 22648 KB Output is correct
27 Correct 22 ms 22648 KB Output is correct
28 Correct 22 ms 22648 KB Output is correct
29 Correct 21 ms 22648 KB Output is correct
30 Correct 21 ms 22648 KB Output is correct
31 Correct 529 ms 32800 KB Output is correct
32 Correct 138 ms 27564 KB Output is correct
33 Correct 507 ms 30888 KB Output is correct
34 Correct 457 ms 31140 KB Output is correct
35 Correct 551 ms 32808 KB Output is correct
36 Correct 553 ms 32676 KB Output is correct
37 Correct 396 ms 30504 KB Output is correct
38 Correct 408 ms 30496 KB Output is correct
39 Correct 342 ms 30376 KB Output is correct
40 Correct 351 ms 30372 KB Output is correct
41 Correct 371 ms 30500 KB Output is correct
42 Correct 369 ms 30628 KB Output is correct
43 Correct 110 ms 30756 KB Output is correct
44 Correct 378 ms 30496 KB Output is correct
45 Correct 370 ms 30492 KB Output is correct
46 Correct 359 ms 30372 KB Output is correct
47 Correct 238 ms 30244 KB Output is correct
48 Correct 250 ms 30240 KB Output is correct
49 Correct 280 ms 30372 KB Output is correct
50 Correct 284 ms 30496 KB Output is correct
51 Correct 283 ms 30244 KB Output is correct
52 Correct 488 ms 38564 KB Output is correct
53 Correct 447 ms 36772 KB Output is correct
54 Correct 475 ms 34728 KB Output is correct
55 Correct 392 ms 33052 KB Output is correct
56 Correct 411 ms 34396 KB Output is correct
57 Correct 368 ms 31268 KB Output is correct
58 Correct 396 ms 32928 KB Output is correct
59 Correct 411 ms 34468 KB Output is correct
60 Correct 375 ms 31268 KB Output is correct
61 Correct 151 ms 37400 KB Output is correct
62 Correct 490 ms 38696 KB Output is correct
63 Correct 482 ms 35240 KB Output is correct
64 Correct 470 ms 33952 KB Output is correct
65 Correct 404 ms 31528 KB Output is correct
66 Correct 375 ms 30632 KB Output is correct
67 Correct 351 ms 29736 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 22648 KB Output is correct
2 Correct 20 ms 22648 KB Output is correct
3 Correct 22 ms 22648 KB Output is correct
4 Correct 20 ms 22648 KB Output is correct
5 Correct 20 ms 22520 KB Output is correct
6 Correct 21 ms 22648 KB Output is correct
7 Correct 21 ms 22776 KB Output is correct
8 Correct 21 ms 22776 KB Output is correct
9 Correct 22 ms 22776 KB Output is correct
10 Correct 21 ms 22648 KB Output is correct
11 Correct 20 ms 22648 KB Output is correct
12 Correct 21 ms 22520 KB Output is correct
13 Correct 20 ms 22648 KB Output is correct
14 Correct 21 ms 22776 KB Output is correct
15 Correct 21 ms 22648 KB Output is correct
16 Correct 22 ms 22776 KB Output is correct
17 Correct 21 ms 22648 KB Output is correct
18 Correct 20 ms 22776 KB Output is correct
19 Correct 21 ms 22776 KB Output is correct
20 Correct 22 ms 22648 KB Output is correct
21 Correct 21 ms 22776 KB Output is correct
22 Correct 22 ms 22776 KB Output is correct
23 Correct 21 ms 22780 KB Output is correct
24 Correct 24 ms 22776 KB Output is correct
25 Correct 21 ms 22648 KB Output is correct
26 Correct 22 ms 22648 KB Output is correct
27 Correct 22 ms 22648 KB Output is correct
28 Correct 22 ms 22648 KB Output is correct
29 Correct 21 ms 22648 KB Output is correct
30 Correct 21 ms 22648 KB Output is correct
31 Correct 529 ms 32800 KB Output is correct
32 Correct 138 ms 27564 KB Output is correct
33 Correct 507 ms 30888 KB Output is correct
34 Correct 457 ms 31140 KB Output is correct
35 Correct 551 ms 32808 KB Output is correct
36 Correct 553 ms 32676 KB Output is correct
37 Correct 396 ms 30504 KB Output is correct
38 Correct 408 ms 30496 KB Output is correct
39 Correct 342 ms 30376 KB Output is correct
40 Correct 351 ms 30372 KB Output is correct
41 Correct 371 ms 30500 KB Output is correct
42 Correct 369 ms 30628 KB Output is correct
43 Correct 110 ms 30756 KB Output is correct
44 Correct 378 ms 30496 KB Output is correct
45 Correct 370 ms 30492 KB Output is correct
46 Correct 359 ms 30372 KB Output is correct
47 Correct 238 ms 30244 KB Output is correct
48 Correct 250 ms 30240 KB Output is correct
49 Correct 280 ms 30372 KB Output is correct
50 Correct 284 ms 30496 KB Output is correct
51 Correct 283 ms 30244 KB Output is correct
52 Correct 2096 ms 61892 KB Output is correct
53 Correct 1195 ms 55444 KB Output is correct
54 Correct 1317 ms 84460 KB Output is correct
55 Correct 2031 ms 65784 KB Output is correct
56 Correct 1193 ms 55280 KB Output is correct
57 Correct 1154 ms 55280 KB Output is correct
58 Correct 1317 ms 84460 KB Output is correct
59 Correct 2017 ms 65948 KB Output is correct
60 Correct 2021 ms 59120 KB Output is correct
61 Correct 1466 ms 55720 KB Output is correct
62 Correct 1095 ms 55452 KB Output is correct
63 Correct 1280 ms 55720 KB Output is correct
64 Correct 3963 ms 58856 KB Output is correct
65 Correct 566 ms 53372 KB Output is correct
66 Correct 3636 ms 69736 KB Output is correct
67 Correct 2727 ms 98280 KB Output is correct
68 Correct 3336 ms 75368 KB Output is correct
69 Correct 3348 ms 79224 KB Output is correct
70 Correct 3468 ms 68952 KB Output is correct
71 Correct 3519 ms 69412 KB Output is correct
72 Correct 2896 ms 99540 KB Output is correct
73 Correct 3636 ms 78248 KB Output is correct
74 Correct 3990 ms 72808 KB Output is correct
75 Correct 3992 ms 70504 KB Output is correct
76 Correct 1559 ms 68380 KB Output is correct
77 Correct 1491 ms 67580 KB Output is correct
78 Correct 1756 ms 68836 KB Output is correct
79 Correct 1980 ms 70108 KB Output is correct
80 Correct 1826 ms 68720 KB Output is correct
81 Correct 488 ms 38564 KB Output is correct
82 Correct 447 ms 36772 KB Output is correct
83 Correct 475 ms 34728 KB Output is correct
84 Correct 392 ms 33052 KB Output is correct
85 Correct 411 ms 34396 KB Output is correct
86 Correct 368 ms 31268 KB Output is correct
87 Correct 396 ms 32928 KB Output is correct
88 Correct 411 ms 34468 KB Output is correct
89 Correct 375 ms 31268 KB Output is correct
90 Correct 151 ms 37400 KB Output is correct
91 Correct 490 ms 38696 KB Output is correct
92 Correct 482 ms 35240 KB Output is correct
93 Correct 470 ms 33952 KB Output is correct
94 Correct 404 ms 31528 KB Output is correct
95 Correct 375 ms 30632 KB Output is correct
96 Correct 351 ms 29736 KB Output is correct
97 Correct 3468 ms 100356 KB Output is correct
98 Correct 589 ms 46576 KB Output is correct
99 Correct 4449 ms 64236 KB Output is correct
100 Correct 3350 ms 92700 KB Output is correct
101 Correct 3895 ms 81268 KB Output is correct
102 Execution timed out 5045 ms 69880 KB Time limit exceeded
103 Halted 0 ms 0 KB -