Submission #776865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776865	2023-07-08T10:41:00 Z	marvinthang	Road Construction (JOI21_road_construction)	C++17	100 / 100	1190 ms	13516 KB

road_construction

/*************************************
*    author: marvinthang             *
*    created: 08.07.2023 17:25:42    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

const int MAX = 2.5e5 + 5;

int N, K;
pair <long long, long long> A[MAX];

void init(void) {
	cin >> N >> K;
	REP(i, N) {
		int x, y; cin >> x >> y;
		A[i] = make_pair(x + y, x - y);
	}
}

bool check(long long m) {
	multiset <long long> s;
	int j = 0;
	int cnt = 0;
	REP(i, N) {
		while (A[i].fi - A[j].fi > m) s.erase(s.find(A[j++].se));
		for (auto it = s.lower_bound(A[i].se - m); it != s.end() && *it <= A[i].se + m; ++it) {
			if (++cnt >= K) return true;
		}
		s.insert(A[i].se);
	}
	return false;
}

void process(void) {
	sort(A, A + N);
	long long l = 0, r = 4e9;
	while (l <= r) {
		long long m = l + r >> 1;
		if (check(m)) r = m - 1;
		else l = m + 1;
	}
	multiset <pair <long long, long long>> s;
	--l;
	vector <long long> v;
	int j = 0;
	REP(i, N) {
		while (A[i].fi - A[j].fi > l) {
			s.erase(make_pair(A[j].se, A[j].fi));
			j++;
		}
		for (auto it = s.lower_bound(make_pair(A[i].se - l, -2e9)); it != s.end() && it->fi <= A[i].se + l; ++it) {
			v.push_back(max(abs(A[i].fi - it->se), abs(A[i].se - it->fi)));
		}
		s.emplace(A[i].se, A[i].fi);
	}
	sort(ALL(v));
	for (long long x: v) cout << x << '\n';
	K -= (int) v.size();
	while (K--) cout << l + 1 << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("road_construction");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

road_construction.cpp: In function 'void process()':
road_construction.cpp:76:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   long long m = l + r >> 1;
      |                 ~~^~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:102:2: note: in expansion of macro 'file'
  102 |  file("road_construction");
      |  ^~~~
road_construction.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:102:2: note: in expansion of macro 'file'
  102 |  file("road_construction");
      |  ^~~~

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	4944 KB	Output is correct
2	Correct	72 ms	4968 KB	Output is correct
3	Correct	65 ms	5104 KB	Output is correct
4	Correct	63 ms	5104 KB	Output is correct
5	Correct	66 ms	3840 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	250 ms	7904 KB	Output is correct
2	Correct	250 ms	10596 KB	Output is correct
3	Correct	58 ms	4912 KB	Output is correct
4	Correct	214 ms	10400 KB	Output is correct
5	Correct	247 ms	10460 KB	Output is correct
6	Correct	194 ms	10580 KB	Output is correct
7	Correct	188 ms	10064 KB	Output is correct

Subtask #3

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	5096 KB	Output is correct
2	Correct	211 ms	9308 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	101 ms	7124 KB	Output is correct
5	Correct	231 ms	9492 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	5096 KB	Output is correct
2	Correct	211 ms	9308 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	101 ms	7124 KB	Output is correct
5	Correct	231 ms	9492 KB	Output is correct
6	Correct	303 ms	9304 KB	Output is correct
7	Correct	278 ms	9320 KB	Output is correct
8	Correct	1 ms	328 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	226 ms	9248 KB	Output is correct
11	Correct	90 ms	7140 KB	Output is correct
12	Correct	231 ms	9552 KB	Output is correct

Subtask #5

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	4944 KB	Output is correct
2	Correct	72 ms	4968 KB	Output is correct
3	Correct	65 ms	5104 KB	Output is correct
4	Correct	63 ms	5104 KB	Output is correct
5	Correct	66 ms	3840 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	563 ms	6008 KB	Output is correct
8	Correct	564 ms	5964 KB	Output is correct
9	Correct	75 ms	5100 KB	Output is correct
10	Correct	321 ms	5212 KB	Output is correct
11	Correct	196 ms	5132 KB	Output is correct
12	Correct	214 ms	3932 KB	Output is correct
13	Correct	279 ms	4480 KB	Output is correct

Subtask #6

35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	4944 KB	Output is correct
2	Correct	72 ms	4968 KB	Output is correct
3	Correct	65 ms	5104 KB	Output is correct
4	Correct	63 ms	5104 KB	Output is correct
5	Correct	66 ms	3840 KB	Output is correct
6	Correct	2 ms	340 KB	Output is correct
7	Correct	250 ms	7904 KB	Output is correct
8	Correct	250 ms	10596 KB	Output is correct
9	Correct	58 ms	4912 KB	Output is correct
10	Correct	214 ms	10400 KB	Output is correct
11	Correct	247 ms	10460 KB	Output is correct
12	Correct	194 ms	10580 KB	Output is correct
13	Correct	188 ms	10064 KB	Output is correct
14	Correct	173 ms	5096 KB	Output is correct
15	Correct	211 ms	9308 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	101 ms	7124 KB	Output is correct
18	Correct	231 ms	9492 KB	Output is correct
19	Correct	303 ms	9304 KB	Output is correct
20	Correct	278 ms	9320 KB	Output is correct
21	Correct	1 ms	328 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	226 ms	9248 KB	Output is correct
24	Correct	90 ms	7140 KB	Output is correct
25	Correct	231 ms	9552 KB	Output is correct
26	Correct	563 ms	6008 KB	Output is correct
27	Correct	564 ms	5964 KB	Output is correct
28	Correct	75 ms	5100 KB	Output is correct
29	Correct	321 ms	5212 KB	Output is correct
30	Correct	196 ms	5132 KB	Output is correct
31	Correct	214 ms	3932 KB	Output is correct
32	Correct	279 ms	4480 KB	Output is correct
33	Correct	1190 ms	13368 KB	Output is correct
34	Correct	1188 ms	13516 KB	Output is correct
35	Correct	816 ms	12616 KB	Output is correct
36	Correct	381 ms	11484 KB	Output is correct
37	Correct	370 ms	11468 KB	Output is correct
38	Correct	447 ms	12240 KB	Output is correct