oj.uz

Submission #243040

# Submission time Handle Problem Language Result Execution time Memory
243040 2020-06-30T08:05:58 Z atoiz New Home (APIO18_new_home) C++14
100 / 100
 3760 ms 233148 KB 
/*input
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7

1 1 1
100000000 1 1 1
1 1

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




*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <map>
#include <set>

using namespace std;

const int MAXN = 300007, INF = 900 * 1000 * 1000;

void minimize(int &x, int y) { x = (x < y ? x : y); }
void maximize(int &x, int y) { x = (x > y ? x : y); }

struct SegmentTree
{
	int N;
	vector<int> A;

	void init(int _N)
	{
		for (N = _N + 5; N & (N - 1); ++N);
		A.assign(N * 2, INF);
	}

	void modify(int l, int r, int x)
	{
		for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
			if (l & 1) minimize(A[l++], x);
			if (r & 1) minimize(A[--r], x);
		}
	}

	int get(int i)
	{
		int ans = INF;
		for (i += N; i >= 1; i >>= 1) minimize(ans, A[i]);
		return ans;
	}
} it;

int N, Q, K;
struct Store { int x, t, a, b, i; } S[MAXN];
struct Border 
{ 
	int x, t, a, b, v; 
	Border(int _x = 0, int _t = 0, int _a = 0, int _b = 0, int _v = 0): x(_x), t(_t), a(_a), b(_b), v(_v) {}
};
struct Query
{
	int x, y, i;
};

int last[MAXN * 2], ans[MAXN];
map<int, vector<int>> events;
set<pair<int, int>> curSet[MAXN];
vector<Border> rightBorder, leftBorder;
vector<Query> queries;
vector<int> times;

void addBorder(pair<int, int> p, pair<int, int> q, int t, int curTime)
{
	int i = p.second, j = q.second;
	int x = (p.first + q.first) >> 1;
	// cout << "add " << i << ' ' << j << ' ' << x << ' ' << curTime << endl;
	int a = last[i], b = curTime;
	last[i] = curTime;
	// if (t == 2) cout << "border " << x << ' ' << a << ' ' << b << ' ' << t << ": " << p.first << ' ' << q.first << " - " << i << endl;
	if (i > N && j > N) {
		leftBorder.emplace_back(-INF, t, a, b, INF);
		rightBorder.emplace_back(INF, t, a, b, -INF);
	} else {
		leftBorder.emplace_back(x, t, a, b, q.first);
		rightBorder.emplace_back(x, t, a, b, p.first);
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K >> Q;
	for (int i = 1; i <= N; ++i) {
		cin >> S[i].x >> S[i].t >> S[i].a >> S[i].b; S[i].i = i;
		// cout << i << ": " << S[i].a << ' ' << S[i].b << endl;
		S[i].x *= 2, ++S[i].b;
		events[S[i].a].push_back(i);
		events[S[i].b].push_back(i);
	}

	for (int t = 1; t <= K; ++t) {
		last[N + t] = 0;
		curSet[t].emplace(-INF, N + t);
		curSet[t].emplace(INF, N + t);
	}

	for (auto ts : events) {
		int curTime = ts.first;
		for (int i : ts.second) {
			int t = S[i].t, x = S[i].x;	
			if (S[i].a == curTime) {
				last[i] = curTime;
				curSet[t].emplace(x, i);
				auto j = curSet[t].find(make_pair(x, i));
				addBorder(*prev(j), *next(j), t, curTime);
			} else {
				auto j = curSet[t].find(make_pair(x, i));
				addBorder(*prev(j), *j, t, curTime);
				addBorder(*j, *next(j), t, curTime);
				curSet[t].erase(j);
			}
		}
	}

	for (int t = 1; t <= K; ++t) addBorder(*curSet[t].begin(), *curSet[t].rbegin(), t, INF);

	times.push_back(-INF);
	for (auto &b : leftBorder) times.push_back(b.a), times.push_back(b.b);
	for (auto &b : rightBorder) times.push_back(b.a), times.push_back(b.b);
	sort(times.begin(), times.end());
	times.erase(unique(times.begin(), times.end()), times.end());
	// for (int x : times) cout << x << ' '; cout << endl;
	for (auto &b : leftBorder) {
		b.a = (int) (upper_bound(times.begin(), times.end(), b.a) - times.begin());
		b.b = (int) (upper_bound(times.begin(), times.end(), b.b) - times.begin());
	}
	for (auto &b : rightBorder) {
		b.a = (int) (upper_bound(times.begin(), times.end(), b.a) - times.begin());
		b.b = (int) (upper_bound(times.begin(), times.end(), b.b) - times.begin());
	}

	queries.resize(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> queries[i].x >> queries[i].y;
		queries[i].x *= 2;
		queries[i].y = (int) (upper_bound(times.begin(), times.end(), queries[i].y) - times.begin());
		queries[i].i = i;
	}
	sort(leftBorder.begin(), leftBorder.end(), [&](Border a, Border b) { return a.x < b.x; });
	sort(rightBorder.begin(), rightBorder.end(), [&](Border a, Border b) { return a.x > b.x; });
	for (int i = 0; i < Q; ++i) ans[i] = -1;

	sort(queries.begin(), queries.end(), [&](Query p, Query q) { return p.x > q.x; });
	it.init((int) times.size());
	auto b = rightBorder.begin();
	for (auto &q : queries) {
		for (; b != rightBorder.end() && b->x >= q.x; ++b) {
			// cout << "r " << b->x << ": " << b->a << ' ' << b->b << ' ' << b->v << endl;
			it.modify(b->a, b->b, b->v);
		}
		int x = it.get(q.y);
		// cout << "g " << q.y << ": " << q.x << " - " << x << ", " << q.i << endl;
		if (x != INF) maximize(ans[q.i], q.x - x);
	}
	// cout << "-" << endl;

	reverse(queries.begin(), queries.end());
	it.init((int) times.size());
	b = leftBorder.begin();
	for (auto &q : queries) {
		for (; b != leftBorder.end() && b->x <= q.x; ++b) {
			// cout << "l " << b->x << ": " << b->a << ' ' << b->b << ' ' << b->v << endl;
			it.modify(b->a, b->b, -b->v);
		}
		int x = -it.get(q.y);
		// cout << "g " << q.y << ": " << q.x << " - " << x << ", " << q.i << endl;
		if (x != -INF) maximize(ans[q.i], x - q.x);
	}
	// cout << "-" << endl;

	for (int i = 0; i < Q; ++i) {
		if (ans[i] >= 200 * 1000 * 1000) ans[i] = -2;
		cout << (ans[i] / 2) << '\n';
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 15 ms 14720 KB Output is correct
7 Correct 14 ms 14720 KB Output is correct
8 Correct 15 ms 14720 KB Output is correct
9 Correct 15 ms 14720 KB Output is correct
10 Correct 15 ms 14720 KB Output is correct
11 Correct 15 ms 14720 KB Output is correct
12 Correct 14 ms 14720 KB Output is correct
13 Correct 15 ms 14720 KB Output is correct
14 Correct 14 ms 14768 KB Output is correct
15 Correct 16 ms 14720 KB Output is correct
16 Correct 15 ms 14720 KB Output is correct
17 Correct 15 ms 14720 KB Output is correct
18 Correct 15 ms 14720 KB Output is correct
19 Correct 14 ms 14720 KB Output is correct
20 Correct 15 ms 14720 KB Output is correct
21 Correct 14 ms 14720 KB Output is correct
22 Correct 15 ms 14720 KB Output is correct
23 Correct 15 ms 14720 KB Output is correct
24 Correct 16 ms 14720 KB Output is correct
25 Correct 17 ms 14720 KB Output is correct
26 Correct 15 ms 14720 KB Output is correct
27 Correct 14 ms 14592 KB Output is correct
28 Correct 14 ms 14720 KB Output is correct
29 Correct 15 ms 14720 KB Output is correct
30 Correct 14 ms 14720 KB Output is correct
31 Correct 480 ms 44800 KB Output is correct
32 Correct 147 ms 31828 KB Output is correct
33 Correct 517 ms 46532 KB Output is correct
34 Correct 455 ms 46848 KB Output is correct
35 Correct 485 ms 46868 KB Output is correct
36 Correct 487 ms 46512 KB Output is correct
37 Correct 400 ms 46640 KB Output is correct
38 Correct 380 ms 46396 KB Output is correct
39 Correct 345 ms 46428 KB Output is correct
40 Correct 357 ms 46520 KB Output is correct
41 Correct 368 ms 46784 KB Output is correct
42 Correct 380 ms 46584 KB Output is correct
43 Correct 115 ms 33556 KB Output is correct
44 Correct 362 ms 46752 KB Output is correct
45 Correct 353 ms 46876 KB Output is correct
46 Correct 312 ms 46644 KB Output is correct
47 Correct 284 ms 45340 KB Output is correct
48 Correct 285 ms 44996 KB Output is correct
49 Correct 311 ms 45600 KB Output is correct
50 Correct 330 ms 46372 KB Output is correct
51 Correct 312 ms 45556 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 971 ms 108164 KB Output is correct
2 Correct 1098 ms 105084 KB Output is correct
3 Correct 1062 ms 169600 KB Output is correct
4 Correct 990 ms 122496 KB Output is correct
5 Correct 1146 ms 104404 KB Output is correct
6 Correct 1236 ms 104788 KB Output is correct
7 Correct 768 ms 169736 KB Output is correct
8 Correct 731 ms 122580 KB Output is correct
9 Correct 723 ms 111872 KB Output is correct
10 Correct 763 ms 105952 KB Output is correct
11 Correct 716 ms 103884 KB Output is correct
12 Correct 703 ms 105564 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2029 ms 131568 KB Output is correct
2 Correct 766 ms 95988 KB Output is correct
3 Correct 2666 ms 136288 KB Output is correct
4 Correct 2245 ms 199108 KB Output is correct
5 Correct 2124 ms 145876 KB Output is correct
6 Correct 2135 ms 151912 KB Output is correct
7 Correct 2557 ms 135832 KB Output is correct
8 Correct 2324 ms 136444 KB Output is correct
9 Correct 2035 ms 200248 KB Output is correct
10 Correct 1920 ms 149480 KB Output is correct
11 Correct 1940 ms 140532 KB Output is correct
12 Correct 1908 ms 137504 KB Output is correct
13 Correct 1160 ms 132780 KB Output is correct
14 Correct 1107 ms 131384 KB Output is correct
15 Correct 1235 ms 134280 KB Output is correct
16 Correct 1374 ms 136256 KB Output is correct
17 Correct 1277 ms 133644 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 15 ms 14720 KB Output is correct
7 Correct 14 ms 14720 KB Output is correct
8 Correct 15 ms 14720 KB Output is correct
9 Correct 15 ms 14720 KB Output is correct
10 Correct 15 ms 14720 KB Output is correct
11 Correct 15 ms 14720 KB Output is correct
12 Correct 14 ms 14720 KB Output is correct
13 Correct 15 ms 14720 KB Output is correct
14 Correct 14 ms 14768 KB Output is correct
15 Correct 16 ms 14720 KB Output is correct
16 Correct 15 ms 14720 KB Output is correct
17 Correct 15 ms 14720 KB Output is correct
18 Correct 15 ms 14720 KB Output is correct
19 Correct 14 ms 14720 KB Output is correct
20 Correct 15 ms 14720 KB Output is correct
21 Correct 14 ms 14720 KB Output is correct
22 Correct 15 ms 14720 KB Output is correct
23 Correct 15 ms 14720 KB Output is correct
24 Correct 16 ms 14720 KB Output is correct
25 Correct 17 ms 14720 KB Output is correct
26 Correct 15 ms 14720 KB Output is correct
27 Correct 14 ms 14592 KB Output is correct
28 Correct 14 ms 14720 KB Output is correct
29 Correct 15 ms 14720 KB Output is correct
30 Correct 14 ms 14720 KB Output is correct
31 Correct 480 ms 44800 KB Output is correct
32 Correct 147 ms 31828 KB Output is correct
33 Correct 517 ms 46532 KB Output is correct
34 Correct 455 ms 46848 KB Output is correct
35 Correct 485 ms 46868 KB Output is correct
36 Correct 487 ms 46512 KB Output is correct
37 Correct 400 ms 46640 KB Output is correct
38 Correct 380 ms 46396 KB Output is correct
39 Correct 345 ms 46428 KB Output is correct
40 Correct 357 ms 46520 KB Output is correct
41 Correct 368 ms 46784 KB Output is correct
42 Correct 380 ms 46584 KB Output is correct
43 Correct 115 ms 33556 KB Output is correct
44 Correct 362 ms 46752 KB Output is correct
45 Correct 353 ms 46876 KB Output is correct
46 Correct 312 ms 46644 KB Output is correct
47 Correct 284 ms 45340 KB Output is correct
48 Correct 285 ms 44996 KB Output is correct
49 Correct 311 ms 45600 KB Output is correct
50 Correct 330 ms 46372 KB Output is correct
51 Correct 312 ms 45556 KB Output is correct
52 Correct 533 ms 55760 KB Output is correct
53 Correct 536 ms 55680 KB Output is correct
54 Correct 500 ms 49536 KB Output is correct
55 Correct 383 ms 49916 KB Output is correct
56 Correct 398 ms 51188 KB Output is correct
57 Correct 363 ms 47616 KB Output is correct
58 Correct 424 ms 49852 KB Output is correct
59 Correct 427 ms 51284 KB Output is correct
60 Correct 384 ms 47652 KB Output is correct
61 Correct 136 ms 42904 KB Output is correct
62 Correct 509 ms 55888 KB Output is correct
63 Correct 487 ms 51172 KB Output is correct
64 Correct 483 ms 49660 KB Output is correct
65 Correct 431 ms 47660 KB Output is correct
66 Correct 408 ms 46884 KB Output is correct
67 Correct 151 ms 33024 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14464 KB Output is correct
3 Correct 13 ms 14464 KB Output is correct
4 Correct 13 ms 14464 KB Output is correct
5 Correct 14 ms 14592 KB Output is correct
6 Correct 15 ms 14720 KB Output is correct
7 Correct 14 ms 14720 KB Output is correct
8 Correct 15 ms 14720 KB Output is correct
9 Correct 15 ms 14720 KB Output is correct
10 Correct 15 ms 14720 KB Output is correct
11 Correct 15 ms 14720 KB Output is correct
12 Correct 14 ms 14720 KB Output is correct
13 Correct 15 ms 14720 KB Output is correct
14 Correct 14 ms 14768 KB Output is correct
15 Correct 16 ms 14720 KB Output is correct
16 Correct 15 ms 14720 KB Output is correct
17 Correct 15 ms 14720 KB Output is correct
18 Correct 15 ms 14720 KB Output is correct
19 Correct 14 ms 14720 KB Output is correct
20 Correct 15 ms 14720 KB Output is correct
21 Correct 14 ms 14720 KB Output is correct
22 Correct 15 ms 14720 KB Output is correct
23 Correct 15 ms 14720 KB Output is correct
24 Correct 16 ms 14720 KB Output is correct
25 Correct 17 ms 14720 KB Output is correct
26 Correct 15 ms 14720 KB Output is correct
27 Correct 14 ms 14592 KB Output is correct
28 Correct 14 ms 14720 KB Output is correct
29 Correct 15 ms 14720 KB Output is correct
30 Correct 14 ms 14720 KB Output is correct
31 Correct 480 ms 44800 KB Output is correct
32 Correct 147 ms 31828 KB Output is correct
33 Correct 517 ms 46532 KB Output is correct
34 Correct 455 ms 46848 KB Output is correct
35 Correct 485 ms 46868 KB Output is correct
36 Correct 487 ms 46512 KB Output is correct
37 Correct 400 ms 46640 KB Output is correct
38 Correct 380 ms 46396 KB Output is correct
39 Correct 345 ms 46428 KB Output is correct
40 Correct 357 ms 46520 KB Output is correct
41 Correct 368 ms 46784 KB Output is correct
42 Correct 380 ms 46584 KB Output is correct
43 Correct 115 ms 33556 KB Output is correct
44 Correct 362 ms 46752 KB Output is correct
45 Correct 353 ms 46876 KB Output is correct
46 Correct 312 ms 46644 KB Output is correct
47 Correct 284 ms 45340 KB Output is correct
48 Correct 285 ms 44996 KB Output is correct
49 Correct 311 ms 45600 KB Output is correct
50 Correct 330 ms 46372 KB Output is correct
51 Correct 312 ms 45556 KB Output is correct
52 Correct 971 ms 108164 KB Output is correct
53 Correct 1098 ms 105084 KB Output is correct
54 Correct 1062 ms 169600 KB Output is correct
55 Correct 990 ms 122496 KB Output is correct
56 Correct 1146 ms 104404 KB Output is correct
57 Correct 1236 ms 104788 KB Output is correct
58 Correct 768 ms 169736 KB Output is correct
59 Correct 731 ms 122580 KB Output is correct
60 Correct 723 ms 111872 KB Output is correct
61 Correct 763 ms 105952 KB Output is correct
62 Correct 716 ms 103884 KB Output is correct
63 Correct 703 ms 105564 KB Output is correct
64 Correct 2029 ms 131568 KB Output is correct
65 Correct 766 ms 95988 KB Output is correct
66 Correct 2666 ms 136288 KB Output is correct
67 Correct 2245 ms 199108 KB Output is correct
68 Correct 2124 ms 145876 KB Output is correct
69 Correct 2135 ms 151912 KB Output is correct
70 Correct 2557 ms 135832 KB Output is correct
71 Correct 2324 ms 136444 KB Output is correct
72 Correct 2035 ms 200248 KB Output is correct
73 Correct 1920 ms 149480 KB Output is correct
74 Correct 1940 ms 140532 KB Output is correct
75 Correct 1908 ms 137504 KB Output is correct
76 Correct 1160 ms 132780 KB Output is correct
77 Correct 1107 ms 131384 KB Output is correct
78 Correct 1235 ms 134280 KB Output is correct
79 Correct 1374 ms 136256 KB Output is correct
80 Correct 1277 ms 133644 KB Output is correct
81 Correct 533 ms 55760 KB Output is correct
82 Correct 536 ms 55680 KB Output is correct
83 Correct 500 ms 49536 KB Output is correct
84 Correct 383 ms 49916 KB Output is correct
85 Correct 398 ms 51188 KB Output is correct
86 Correct 363 ms 47616 KB Output is correct
87 Correct 424 ms 49852 KB Output is correct
88 Correct 427 ms 51284 KB Output is correct
89 Correct 384 ms 47652 KB Output is correct
90 Correct 136 ms 42904 KB Output is correct
91 Correct 509 ms 55888 KB Output is correct
92 Correct 487 ms 51172 KB Output is correct
93 Correct 483 ms 49660 KB Output is correct
94 Correct 431 ms 47660 KB Output is correct
95 Correct 408 ms 46884 KB Output is correct
96 Correct 151 ms 33024 KB Output is correct
97 Correct 3282 ms 232876 KB Output is correct
98 Correct 746 ms 96608 KB Output is correct
99 Correct 3331 ms 170156 KB Output is correct
100 Correct 3283 ms 232608 KB Output is correct
101 Correct 3384 ms 185740 KB Output is correct
102 Correct 3760 ms 169860 KB Output is correct
103 Correct 2367 ms 170192 KB Output is correct
104 Correct 2466 ms 169728 KB Output is correct
105 Correct 1934 ms 169700 KB Output is correct
106 Correct 1992 ms 169712 KB Output is correct
107 Correct 2460 ms 183108 KB Output is correct
108 Correct 2562 ms 203520 KB Output is correct
109 Correct 2320 ms 176076 KB Output is correct
110 Correct 2583 ms 186740 KB Output is correct
111 Correct 2738 ms 210672 KB Output is correct
112 Correct 2618 ms 176164 KB Output is correct
113 Correct 669 ms 168320 KB Output is correct
114 Correct 3268 ms 233148 KB Output is correct
115 Correct 3367 ms 210476 KB Output is correct
116 Correct 3268 ms 186708 KB Output is correct
117 Correct 3236 ms 176812 KB Output is correct
118 Correct 2538 ms 172104 KB Output is correct
119 Correct 785 ms 103500 KB Output is correct
120 Correct 1406 ms 157792 KB Output is correct
121 Correct 1537 ms 164768 KB Output is correct
122 Correct 1471 ms 163364 KB Output is correct
123 Correct 1660 ms 166804 KB Output is correct
124 Correct 1752 ms 169564 KB Output is correct
125 Correct 1597 ms 167472 KB Output is correct
126 Correct 1753 ms 170052 KB Output is correct