Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <vector>
- #include <algorithm>
- #include <set>
- #include <map>
- #include <queue>
- #include <fstream>
- #include <ctime>
- #include <random>
- #include <iomanip>
- #include <bitset>
- using namespace std;
- typedef long long ll;
- #ifdef DEBUG
- const int MAXN = 200;
- #else
- const int MAXN = 1e6 + 200;
- #define cerr if (false) cerr
- #endif
- ll INF = 3e18;
- int MOD = 1e9 + 7;
- int n, m;
- struct V {
- ll x, y, z;
- };
- V st[MAXN];
- V points[MAXN];
- ll t[MAXN];
- int SZ;
- ll get(int pos) {
- ll ans = -INF;
- for (int i = pos + 1; i > 0; i -= i & -i) {
- ans = max(ans, t[i]);
- }
- return ans;
- }
- void upd(int pos, ll x) {
- for (int i = pos + 1; i <= SZ; i += i & -i) {
- t[i] = max(t[i], x);
- }
- }
- int id_y_a[MAXN];
- int id_y_b[MAXN];
- pair<ll, int> y_a[MAXN];
- pair<ll, int> y_b[MAXN];
- bool check(ll mid) {
- int ptr = 0;
- int pnt_y = 0;
- for (int i = 0; i < n; i++) {
- while (ptr < m && y_a[ptr].first - mid > y_b[i].first) {
- id_y_a[y_a[ptr++].second] = pnt_y++;
- }
- id_y_b[y_b[i].second] = pnt_y++;
- }
- while (ptr < m) {
- id_y_a[y_a[ptr++].second] = pnt_y++;
- }
- SZ = pnt_y + 100;
- for (int i = 0; i <= SZ; i++) {
- t[i] = -INF;
- }
- int pnt = 0;
- for (int i = 0; i < m; i++) {
- while (pnt < n && st[pnt].x >= points[i].x - mid) {
- upd(id_y_b[pnt], st[pnt].z);
- pnt++;
- }
- ll bst = get(id_y_a[i]);
- if (bst < points[i].z - mid) {
- return 0;
- }
- }
- return 1;
- }
- void init() {
- }
- void solve() {
- init();
- for (int j = 0; j < m; j++) {
- cin >> points[j].x >> points[j].y >> points[j].z;
- }
- sort(points, points + m, [](V a, V b){
- return a.x > b.x;
- });
- for (int j = 0; j < m; j++) {
- y_a[j] = make_pair(points[j].y, j);
- }
- sort(y_a, y_a + m, [](pair<ll, int> a, pair<ll, int> b){
- return a.first > b.first;
- });
- for (int i = 0; i < n; i++) {
- cin >> st[i].x >> st[i].y >> st[i].z;
- }
- sort(st, st + n, [](V a, V b){
- return a.x > b.x;
- });
- for (int i = 0; i < n; i++) {
- y_b[i] = make_pair(st[i].y, i);
- }
- sort(y_b, y_b + n, [](pair<ll, int> a, pair<ll, int> b){
- return a.first > b.first;
- });
- ll l = -INF;
- ll r = INF;
- while (l + 1 < r) {
- ll mid = (l + r) >> 1;
- if (check(mid)) {
- r = mid;
- }
- else {
- l = mid;
- }
- }
- cout << r << '\n';
- }
- signed main() {
- #ifdef DEBUG
- freopen("D.in", "r", stdin);
- freopen("D.out", "w", stdout);
- #else
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- while (cin >> m >> n) {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement