oj.uz

Submission #581586

# Submission time Handle Problem Language Result Execution time Memory
581586 2022-06-22T19:24:39 Z cheissmart Road Construction (JOI21_road_construction) C++14
100 / 100
 9415 ms 69400 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20792 KB Output is correct
2 Correct 168 ms 20696 KB Output is correct
3 Correct 133 ms 20820 KB Output is correct
4 Correct 132 ms 20896 KB Output is correct
5 Correct 157 ms 19632 KB Output is correct
6 Correct 17 ms 16200 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4932 ms 67348 KB Output is correct
2 Correct 4844 ms 67144 KB Output is correct
3 Correct 130 ms 20696 KB Output is correct
4 Correct 4760 ms 67192 KB Output is correct
5 Correct 4969 ms 66972 KB Output is correct
6 Correct 5011 ms 66976 KB Output is correct
7 Correct 4777 ms 67296 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8047 ms 69248 KB Output is correct
2 Correct 8157 ms 69304 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 4521 ms 67140 KB Output is correct
5 Correct 4797 ms 69400 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8047 ms 69248 KB Output is correct
2 Correct 8157 ms 69304 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 4521 ms 67140 KB Output is correct
5 Correct 4797 ms 69400 KB Output is correct
6 Correct 8182 ms 69108 KB Output is correct
7 Correct 8209 ms 69068 KB Output is correct
8 Correct 7 ms 15980 KB Output is correct
9 Correct 8 ms 15956 KB Output is correct
10 Correct 8061 ms 69204 KB Output is correct
11 Correct 4725 ms 67016 KB Output is correct
12 Correct 4810 ms 69344 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20792 KB Output is correct
2 Correct 168 ms 20696 KB Output is correct
3 Correct 133 ms 20820 KB Output is correct
4 Correct 132 ms 20896 KB Output is correct
5 Correct 157 ms 19632 KB Output is correct
6 Correct 17 ms 16200 KB Output is correct
7 Correct 3524 ms 39308 KB Output is correct
8 Correct 3534 ms 39272 KB Output is correct
9 Correct 132 ms 20848 KB Output is correct
10 Correct 3242 ms 38928 KB Output is correct
11 Correct 3071 ms 39324 KB Output is correct
12 Correct 1704 ms 39304 KB Output is correct
13 Correct 2029 ms 39192 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 20792 KB Output is correct
2 Correct 168 ms 20696 KB Output is correct
3 Correct 133 ms 20820 KB Output is correct
4 Correct 132 ms 20896 KB Output is correct
5 Correct 157 ms 19632 KB Output is correct
6 Correct 17 ms 16200 KB Output is correct
7 Correct 4932 ms 67348 KB Output is correct
8 Correct 4844 ms 67144 KB Output is correct
9 Correct 130 ms 20696 KB Output is correct
10 Correct 4760 ms 67192 KB Output is correct
11 Correct 4969 ms 66972 KB Output is correct
12 Correct 5011 ms 66976 KB Output is correct
13 Correct 4777 ms 67296 KB Output is correct
14 Correct 8047 ms 69248 KB Output is correct
15 Correct 8157 ms 69304 KB Output is correct
16 Correct 7 ms 15956 KB Output is correct
17 Correct 4521 ms 67140 KB Output is correct
18 Correct 4797 ms 69400 KB Output is correct
19 Correct 8182 ms 69108 KB Output is correct
20 Correct 8209 ms 69068 KB Output is correct
21 Correct 7 ms 15980 KB Output is correct
22 Correct 8 ms 15956 KB Output is correct
23 Correct 8061 ms 69204 KB Output is correct
24 Correct 4725 ms 67016 KB Output is correct
25 Correct 4810 ms 69344 KB Output is correct
26 Correct 3524 ms 39308 KB Output is correct
27 Correct 3534 ms 39272 KB Output is correct
28 Correct 132 ms 20848 KB Output is correct
29 Correct 3242 ms 38928 KB Output is correct
30 Correct 3071 ms 39324 KB Output is correct
31 Correct 1704 ms 39304 KB Output is correct
32 Correct 2029 ms 39192 KB Output is correct
33 Correct 9354 ms 68872 KB Output is correct
34 Correct 9415 ms 68888 KB Output is correct
35 Correct 8621 ms 68924 KB Output is correct
36 Correct 4450 ms 69312 KB Output is correct
37 Correct 4527 ms 69096 KB Output is correct
38 Correct 5306 ms 69268 KB Output is correct