oj.uz

답안 #776864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776864 2023-07-08T10:39:53 Z marvinthang Road Construction (JOI21_road_construction) C++17
32 / 100
 575 ms 8048 KB 
/*************************************
*    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 = 2e5 + 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;
	int j = 0;
	vector <long long> v;
	--l;
	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 -= 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

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 4980 KB Output is correct
2 Correct 71 ms 5028 KB Output is correct
3 Correct 65 ms 5100 KB Output is correct
4 Correct 68 ms 5116 KB Output is correct
5 Correct 66 ms 3844 KB Output is correct
6 Correct 2 ms 340 KB Output is correct

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 6704 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 6756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 36 ms 6756 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 4980 KB Output is correct
2 Correct 71 ms 5028 KB Output is correct
3 Correct 65 ms 5100 KB Output is correct
4 Correct 68 ms 5116 KB Output is correct
5 Correct 66 ms 3844 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 575 ms 8048 KB Output is correct
8 Correct 566 ms 8040 KB Output is correct
9 Correct 69 ms 5112 KB Output is correct
10 Correct 325 ms 7340 KB Output is correct
11 Correct 202 ms 7200 KB Output is correct
12 Correct 212 ms 5948 KB Output is correct
13 Correct 283 ms 6548 KB Output is correct

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 4980 KB Output is correct
2 Correct 71 ms 5028 KB Output is correct
3 Correct 65 ms 5100 KB Output is correct
4 Correct 68 ms 5116 KB Output is correct
5 Correct 66 ms 3844 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Runtime error 31 ms 6704 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -