55342023-07-11 21:50:33111Drónfutárcpp14Időlimit túllépés 65/100597ms63884 KiB
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

#define rand() (rand() | rand() << 16)

#define LSB(x) ((x) & -(x))

struct Pt { int x, y; };

int c1(Pt p) { return - p.x + p.y; }
int c2(Pt p) { return + p.x - p.y; }
int c3(Pt p) { return - p.x - p.y; }
int c4(Pt p) { return + p.x + p.y; }

int d1(Pt p) { return + p.x + p.y; }
int d2(Pt p) { return + p.x + p.y; }
int d3(Pt p) { return - p.x + p.y; }
int d4(Pt p) { return - p.x + p.y; }

char* pi = new char[10000000];

unsigned int ru() {
    while (!isdigit(*pi)) {
        pi++;
    }
    int r = 0;
    while (isdigit(*pi)) {
        r *= 10;
        r += *pi - '0';
        pi++;
    }
    return r;
}

vector<Pt> v;

int cmpy(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	if (a.y > b.y) {
		return -1;
    }
    else if (a.y < b.y) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmpxl(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	if (a.x < b.x) {
		return -1;
    }
    else if (a.x > b.x) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmpxh(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	if (a.x > b.x) {
		return -1;
    }
    else if (a.x < b.x) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp1(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c1(a);
	int cb = c1(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp2(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c2(a);
	int cb = c2(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp3(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c3(a);
	int cb = c3(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int cmp4(const void* _a, const void* _b) {
	Pt a = v[*(int*)_a];
	Pt b = v[*(int*)_b];
	int ca = c4(a);
	int cb = c4(b);
	if (ca < cb) {
		return -1;
    }
    else if (ca > cb) {
		return 1;
    }
    else {
		return 0;
    }
}

int main() {
    fread(pi, 10000000, 1, stdin);
//    fread(pi, 10000000, 1, fopen("be2.txt", "r"));
	int N = ru();
	v.resize(N);
	vector<vector<pii>> g(N);
	for (int i = 0; i < N; i++) {
		v[i].x = ru();
		v[i].y = ru();
		g[i].reserve(8);
	}
	vector<int> w(N);
	iota(w.begin(), w.end(), 0);
	vector<vector<int>> f(N + 1);
	vector<vector<int>> t(N + 1);
	// octant 1
	qsort(w.data(), w.size(), sizeof(int), cmpy);
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		f[i].assign(w.begin() + s, w.begin() + e);
		t[i].resize(e - s);
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp1);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d1(v[f[i][j]]) < d1(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h = N - 1;
		while (l != h) {
			int m = (l + h + 1) / 2;
			if (v[w[m]].y == v[w[i]].y) {
				l = m;
			}
			else {
				h = m - 1;
			}
		}
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c1(v[f[j][m]]) < c1(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d1(v[t[j][l]]) < d1(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d1(v[r]) - d1(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	// octant 4
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp4);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d4(v[f[i][j]]) < d4(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h;
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c4(v[f[j][m]]) <= c4(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d4(v[t[j][l]]) < d4(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d4(v[r]) - d4(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	// octant 2
	qsort(w.data(), w.size(), sizeof(int), cmpxh);
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		copy(w.begin() + s, w.begin() + e, f[i].begin());
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp2);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d2(v[f[i][j]]) < d2(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h;
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c2(v[f[j][m]]) <= c2(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d2(v[t[j][l]]) < d2(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d2(v[r]) - d2(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	// octant 3
	qsort(w.data(), w.size(), sizeof(int), cmpxl);
	for (int i = 1; i <= N; i++) {
		int s = i - LSB(i);
		int e = i;
		copy(w.begin() + s, w.begin() + e, f[i].begin());
		qsort(f[i].data(), f[i].size(), sizeof(int), cmp3);
		for (int j = 0, m = 0; j < e - s; j++) {
			if (d3(v[f[i][j]]) < d3(v[f[i][m]])) {
				m = j;
			}
			t[i][j] = f[i][m];
		}
	}
	for (int i = 0; i < N; i++) {
		int l = i, h = N - 1;
		while (l != h) {
			int m = (l + h + 1) / 2;
			if (v[w[m]].x == v[w[i]].x) {
				l = m;
			}
			else {
				h = m - 1;
			}
		}
		int r = -1;
		for (int j = l; j > 0; j -= LSB(j)) {
			l = -1, h = f[j].size() - 1;
			while (l != h) {
				int m = (l + h + 1) / 2;
				if (c3(v[f[j][m]]) < c3(v[w[i]])) {
					l = m;
				}
				else {
					h = m - 1;
				}
			}
			if (l >= 0 && (r == -1 || d3(v[t[j][l]]) < d3(v[r]))) {
				r = t[j][l];
			}
		}
		if (r != -1) {
			int d = d3(v[r]) - d3(v[w[i]]);
			g[w[i]].push_back({r, d});
			g[r].push_back({w[i], d});
		}
	}
	int ans = 0;
	vector<bool> vis(N);
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, 0});
	while (!pq.empty()) {
        pii a = pq.top();
        pq.pop();
        if (vis[a.second]) {
            continue;
        }
        vis[a.second] = true;
		ans = max(ans, a.first);
        for (auto p : g[a.second]) {
            if (!vis[p.first]) {
                pq.push({p.second, p.first});
            }
        }
    }
    cout << ans << endl;
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1964 KiB
2Időlimit túllépés597ms32928 KiB
subtask215/15
3Elfogadva7ms4708 KiB
4Elfogadva7ms4932 KiB
5Elfogadva7ms5064 KiB
6Elfogadva7ms5336 KiB
7Elfogadva3ms5092 KiB
subtask315/15
8Elfogadva7ms4708 KiB
9Elfogadva7ms4932 KiB
10Elfogadva7ms5064 KiB
11Elfogadva7ms5336 KiB
12Elfogadva3ms5092 KiB
13Elfogadva4ms5488 KiB
14Elfogadva7ms5940 KiB
15Elfogadva6ms6228 KiB
16Elfogadva7ms6252 KiB
17Elfogadva7ms6528 KiB
subtask435/35
18Elfogadva7ms4708 KiB
19Elfogadva7ms4932 KiB
20Elfogadva7ms5064 KiB
21Elfogadva7ms5336 KiB
22Elfogadva3ms5092 KiB
23Elfogadva4ms5488 KiB
24Elfogadva7ms5940 KiB
25Elfogadva6ms6228 KiB
26Elfogadva7ms6252 KiB
27Elfogadva7ms6528 KiB
28Elfogadva7ms6500 KiB
29Elfogadva157ms20372 KiB
30Elfogadva250ms27180 KiB
31Elfogadva257ms27740 KiB
32Elfogadva142ms32156 KiB
subtask50/35
33Elfogadva7ms4708 KiB
34Elfogadva7ms4932 KiB
35Elfogadva7ms5064 KiB
36Elfogadva7ms5336 KiB
37Elfogadva3ms5092 KiB
38Elfogadva4ms5488 KiB
39Elfogadva7ms5940 KiB
40Elfogadva6ms6228 KiB
41Elfogadva7ms6252 KiB
42Elfogadva7ms6528 KiB
43Elfogadva7ms6500 KiB
44Elfogadva157ms20372 KiB
45Elfogadva250ms27180 KiB
46Elfogadva257ms27740 KiB
47Elfogadva142ms32156 KiB
48Elfogadva488ms43820 KiB
49Időlimit túllépés545ms63884 KiB
50Időlimit túllépés555ms33300 KiB
51Időlimit túllépés544ms63864 KiB
52Időlimit túllépés560ms33408 KiB