Submission #581586

#	Time	Username	Problem	Language	Result	Execution time	Memory
581586		cheissmart	Road Construction (JOI21_road_construction)	C++14	100 / 100	9415 ms	69400 KiB

road_construction

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 250007;
const ll oo = 1e18;

struct BIT {
	vi bit;
	int n;
	BIT(int _n) {
		n = _n;
		bit.resize(n);
	}
	void add(int pos, int val) {
		assert(pos > 0);
		for(; pos < n; pos += pos & -pos)
			bit[pos] += val;
	}
	int qry(int pos) {
		int res = 0;
		for(; pos; pos -= pos & -pos)
			res += bit[pos];
		return res;
	}
};

pair<ll, int> t[N * 4];
int n;

void upd(int pos, pair<ll, int> val, int v = 1, int tl = 0, int tr = n) {
	if(tr - tl == 1) {
		t[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos < tm)
		upd(pos, val, v * 2, tl, tm);
	else 
		upd(pos, val, v * 2 + 1, tm, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}

pair<ll, int> qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) / 2;
	pair<ll, int> res = {-oo, -INF};
	if(l < tm) res = max(res, qry(l, r, v * 2, tl, tm));
	if(r > tm) res = max(res, qry(l, r, v * 2 + 1, tm, tr));
	return res;
}


signed main()
{
	IO_OP;

	memset(t, 0xc0, sizeof t);

	int k;
	cin >> n >> k;
	V<ll> x(n), y(n), X(n), Y(n);
	V<array<ll, 3>> aux;
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		X[i] = x[i] + y[i], Y[i] = x[i] - y[i];
		aux.PB({X[i], Y[i], i});
	}
	sort(ALL(aux));

	V<ll> hebe = Y;
	sort(ALL(hebe)), hebe.resize(unique(ALL(hebe)) - hebe.begin());

	auto cnt_pairs = [&] (ll m) { // count the number of pairs with distance <= m
		ll ans = 0;
		V<array<ll, 4>> ev;
		for(int i = 0; i < n; i++) {
			ev.PB({X[i] + m, Y[i] - m, Y[i] + m, 1});
			ev.PB({X[i] - m - 1, Y[i] - m, Y[i] + m, -1});
		}
		sort(ALL(ev));
		BIT bit(n + 1);
		int i = 0;
		for(auto [x_val, l, r, op]:ev) {
			while(i < SZ(aux) && aux[i][0] <= x_val) {
				int tt = lower_bound(ALL(hebe), aux[i++][1]) - hebe.begin() + 1;
				bit.add(tt, 1);
			}
			auto qry_less = [&] (ll val) {
				int tt = lower_bound(ALL(hebe), val) - hebe.begin();
				return bit.qry(tt);
			};
			ans += op * (qry_less(r + 1) - qry_less(l));
		}
		ans -= n;
		assert(ans % 2 == 0);
		ans /= 2;
		return ans;
 	};

	ll lb = 0, rb = 4e9 + 7;
	while(lb <= rb) {
		ll mb = (lb + rb) / 2;
		if(cnt_pairs(mb) >= k) {
			rb = mb - 1;
		} else {
			lb = mb + 1;
		}
	}

	auto get_all = [&] (ll m) { 
		V<ll> res;
		V<array<ll, 3>> ev;
		V<pair<ll, int>> aux2;
		for(int i = 0; i < n; i++) {
			ev.PB({X[i] + m + 1, i, -1});
			ev.PB({X[i] - m, i, 1});
			aux2.EB(Y[i] - m, i);
		}
		sort(ALL(ev));
		sort(ALL(aux2));
		vi pos(n);
		for(int i = 0; i < n; i++)
			pos[aux2[i].S] = i;

		auto activate = [&] (int i) {
			upd(pos[i], {Y[i] + m, i});
		};

		auto deactivate = [&] (int i) {
			upd(pos[i], {-oo, -INF});
		};

		int i = 0;
		for(auto[x_val, y_val, _]:aux) {
			while(i < SZ(ev) && ev[i][0] <= x_val) {
				if(ev[i][2] == 1) {
					activate(ev[i][1]);
				} else {
					deactivate(ev[i][1]);
				}
				i++;
			}
			vi todo;
			while(true) {
				int j = upper_bound(ALL(aux2), MP(y_val, INF)) - aux2.begin();
				if(j == 0) break;
				auto[mx, k] = qry(0, j);
				if(mx >= y_val) {
					deactivate(k);
					todo.PB(k);
					if(k < _)
						res.PB(abs(x[k] - x[_]) + abs(y[k] - y[_]));
				} else {
					break;
				}
			}
			for(int k:todo)
				activate(k);
		}
		return res;
 	};

	V<ll> ans = get_all(rb);
	sort(ALL(ans)), assert(SZ(ans) < k);
	while(SZ(ans) < k)
		ans.PB(rb + 1);

	for(ll i:ans)
		cout << i << '\n';

}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:85:26: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   85 |  memset(t, 0xc0, sizeof t);
      |                          ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, int>' declared here
  211 |     struct pair
      |            ^~~~
road_construction.cpp: In lambda function:
road_construction.cpp:111:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  111 |   for(auto [x_val, l, r, op]:ev) {
      |            ^
road_construction.cpp: In lambda function:
road_construction.cpp:162:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  162 |   for(auto[x_val, y_val, _]:aux) {
      |           ^
road_construction.cpp:175:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  175 |     auto[mx, k] = qry(0, j);
      |         ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35