답안 #876079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876079	2023-11-21T08:14:01 Z	marvinthang	새 집 (APIO18_new_home)	C++17	10 / 100	300 ms	33972 KB

new_home

/*************************************
*    author: marvinthang             *
*    created: 21.11.2023 14:25:44    *
*************************************/

#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-- > 0; )
#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 INF = 1e8;

struct Store {
	int x, t, a, b;
	Store(int x, int t, int a, int b): x(x), t(t), a(a), b(b) {}
};

void process(void) {
	int n, q, k; cin >> n >> k >> q;
	vector <vector <int>> pos(k);
	REP(i, n) {
		int x, t, a, b; cin >> x >> t >> a >> b; --t;
		pos[t].push_back(x);
	}
	vector <pair <int, int>> up, down;
	for (auto &pos: pos) {
		sort(ALL(pos));
		if (pos.empty()) {
			REP(i, q) cout << "-1\n";
			return;
		}
		REP(i, pos.size()) {
			int rr = i == (int) pos.size() - 1 ? INF : (pos[i] + pos[i + 1]) / 2;
			up.emplace_back(rr, rr - pos[i]);
			int ll = !i ? 1 : (pos[i - 1] + pos[i] + 1) / 2;
			down.emplace_back(ll, pos[i] - ll);
		}
	}

	sort(ALL(down), [&] (const pair <int, int> &a, const pair <int, int> &b) {
		return pair {a.fi, b.se} < pair {b.fi, a.se};
	});

	int last = 0;
	vector <pair <int, int>> new_down;
	for (auto [x, y]: down) if (x + y > last) {
		last = x + y;
		new_down.emplace_back(x, y);
	}
	down = move(new_down);

	sort(up.rbegin(), up.rend());
	last = INF;
	vector <pair <int, int>> new_up;
	for (auto [x, y]: up) if (x - y < last) {
		last = x - y;
		new_up.emplace_back(x, y);
	}
	up = move(new_up);
	while (q--) {
		int l, y; cin >> l >> y;
		auto it = prev(upper_bound(ALL(down), l, [&] (const int &x, const pair <int, int> &y) { return x < y.fi; }));
		int res = it->se - l + it->fi;
		it = prev(upper_bound(ALL(up), l, [&] (const int &x, const pair <int, int> &y) { return x > y.fi; }));
		res = max(res, it->se - it->fi + l);
		cout << res << '\n';
	}
}

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

Compilation message

new_home.cpp: In function 'int main()':
new_home.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); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:106:2: note: in expansion of macro 'file'
  106 |  file("new_home");
      |  ^~~~
new_home.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); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:106:2: note: in expansion of macro 'file'
  106 |  file("new_home");
      |  ^~~~

Subtask #1
0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #2
0 / 7.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	231 ms	12212 KB	Output is correct
2	Correct	275 ms	17356 KB	Output is correct
3	Correct	240 ms	33608 KB	Output is correct
4	Correct	239 ms	24148 KB	Output is correct
5	Correct	279 ms	25988 KB	Output is correct
6	Correct	300 ms	18384 KB	Output is correct
7	Correct	209 ms	33972 KB	Output is correct
8	Correct	238 ms	23976 KB	Output is correct
9	Correct	220 ms	19668 KB	Output is correct
10	Correct	235 ms	18944 KB	Output is correct
11	Correct	196 ms	16640 KB	Output is correct
12	Correct	234 ms	17320 KB	Output is correct