#1008182 (C++23) No.2885 Range Triangle Collision Decision Queries

提出ソース

結果

問題	No.2885 Range Triangle Collision Decision Queries
ユーザー	hiro1729
提出日時	2024-09-07 22:30:22
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	738 ms / 3,000 ms
コード長	9,464 bytes
コンパイル時間	3,595 ms
コンパイル使用メモリ	253,588 KB
実行使用メモリ	175,488 KB
最終ジャッジ日時	2024-09-07 22:31:05
合計ジャッジ時間	42,181 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	242 ms 6,816 KB
testcase_01	AC	245 ms 6,944 KB
testcase_02	AC	260 ms 6,944 KB
testcase_03	AC	250 ms 6,940 KB
testcase_04	AC	271 ms 6,940 KB
testcase_05	AC	490 ms 175,480 KB
testcase_06	AC	469 ms 175,480 KB
testcase_07	AC	483 ms 175,480 KB
testcase_08	AC	517 ms 175,484 KB
testcase_09	AC	501 ms 175,484 KB
testcase_10	AC	599 ms 175,484 KB
testcase_11	AC	524 ms 175,484 KB
testcase_12	AC	584 ms 175,484 KB
testcase_13	AC	567 ms 175,484 KB
testcase_14	AC	565 ms 175,356 KB
testcase_15	AC	588 ms 175,484 KB
testcase_16	AC	617 ms 175,452 KB
testcase_17	AC	472 ms 175,484 KB
testcase_18	AC	588 ms 175,484 KB
testcase_19	AC	577 ms 175,484 KB
testcase_20	AC	558 ms 175,484 KB
testcase_21	AC	550 ms 175,356 KB
testcase_22	AC	498 ms 175,480 KB
testcase_23	AC	558 ms 175,360 KB
testcase_24	AC	544 ms 175,480 KB
testcase_25	AC	502 ms 175,360 KB
testcase_26	AC	715 ms 175,376 KB
testcase_27	AC	620 ms 175,484 KB
testcase_28	AC	600 ms 175,488 KB
testcase_29	AC	738 ms 175,484 KB
testcase_30	AC	666 ms 175,480 KB
testcase_31	AC	632 ms 175,480 KB
testcase_32	AC	644 ms 175,356 KB
testcase_33	AC	633 ms 175,356 KB
testcase_34	AC	611 ms 175,484 KB
testcase_35	AC	574 ms 175,356 KB
testcase_36	AC	644 ms 175,356 KB
testcase_37	AC	682 ms 175,484 KB
testcase_38	AC	675 ms 175,480 KB
testcase_39	AC	658 ms 175,488 KB
testcase_40	AC	668 ms 175,356 KB
testcase_41	AC	607 ms 175,484 KB
testcase_42	AC	653 ms 175,484 KB
testcase_43	AC	573 ms 175,484 KB
testcase_44	AC	456 ms 175,432 KB
testcase_45	AC	647 ms 174,744 KB
testcase_46	AC	484 ms 174,864 KB
testcase_47	AC	524 ms 175,484 KB
testcase_48	AC	504 ms 175,488 KB
testcase_49	AC	254 ms 6,940 KB
testcase_50	AC	249 ms 6,940 KB
testcase_51	AC	252 ms 6,944 KB
testcase_52	AC	249 ms 6,944 KB
testcase_53	AC	3 ms 6,944 KB
testcase_54	AC	3 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <unistd.h>

namespace hiro1729 {

namespace fastio {

namespace fastin {

namespace reader {

const size_t buf_size = 1 << 18;
char buf[buf_size];
ssize_t wt = 0, rd = 0;

void _read() {
	ssize_t r = read(0, buf, buf_size);
	wt = r;
	rd = 0;
}

inline int _chr() {
	if (rd == wt) [[unlikely]] {
		_read();
	}
	return buf[rd];
}

inline int nxchar() {
	++rd;
	if (rd == wt) _read();
	return _chr();
}

std::string read_str() {
	int ch = _chr();
	while (isspace(ch)) ch = nxchar();
	int rd_first = rd;
	std::string res;
	while (rd <= wt && !isspace(buf[rd])) {
		++rd;
		if (rd == wt) {
			res += std::string(buf, rd_first, wt - rd_first);
			_read();
			rd_first = 0;
		}
	}
	res += std::string(buf, rd_first, rd - rd_first);
	return res;
}

char read_chr() {
	int ch = _chr();
	while (isspace(ch)) ch = nxchar();
	return ch;
}

template<class T> T read_uint() {
	T ret = 0;
	int ch = _chr();
	while (isspace(ch)) ch = nxchar();
	for (; isdigit(ch); ch = nxchar()) ret = ret * 10 + ch - '0';
	return ret;
}

template<class T> T read_int() {
	T ret = 0;
	bool s = true;
	int ch = _chr();
	while (isspace(ch)) ch = nxchar();
	if (ch == '-') {
		s = false;
		ch = nxchar();
	}
	for (; isdigit(ch); ch = nxchar()) ret = ret * 10 + ch - '0';
	return (s ? ret : -ret);
}

template<class T> T read_flt() {
	return stold(read_str());
}

} // namespace reader

inline short Short() { return reader::read_int<short>(); }
inline unsigned short UShort() { return reader::read_uint<unsigned short>(); }
inline int Int() { return reader::read_int<int>(); }
inline unsigned int UInt() { return reader::read_uint<unsigned int>(); }
inline long Long() { return reader::read_int<long>(); }
inline unsigned long ULong() { return reader::read_uint<unsigned long>(); }
inline long long LLong() { return reader::read_int<long long>(); }
inline unsigned long long ULLong() { return reader::read_uint<unsigned long long>(); }
inline __int128_t Int7() { return reader::read_int<__int128_t>(); }
inline __uint128_t UInt7() { return reader::read_uint<__uint128_t>(); }
inline float Float() { return reader::read_flt<float>(); }
inline double Double() { return reader::read_flt<double>(); }
inline long double LDouble() { return reader::read_flt<long double>(); }
inline std::string String() { return reader::read_str(); }
inline char Char() { return reader::read_chr(); }
inline bool Bool() { return reader::read_chr() == '1'; }

inline void _SingleInput(short &n) { n = Short(); }
inline void _SingleInput(unsigned short &n) { n = UShort(); }
inline void _SingleInput(int &n) { n = Int(); }
inline void _SingleInput(unsigned int &n) { n = UInt(); }
inline void _SingleInput(long &n) { n = Long(); }
inline void _SingleInput(unsigned long &n) { n = ULong(); }
inline void _SingleInput(long long &n) { n = LLong(); }
inline void _SingleInput(unsigned long long &n) { n = ULLong(); }
inline void _SingleInput(__int128_t &n) { n = Int7(); }
inline void _SingleInput(__uint128_t &n) { n = UInt7(); }
inline void _SingleInput(float &d) { d = Float(); }
inline void _SingleInput(double &d) { d = Double(); }
inline void _SingleInput(long double &d) { d = LDouble(); }
inline void _SingleInput(std::string &s) { s = String(); }
inline void _SingleInput(char &c) { c = Char(); }
inline void _SingleInput(bool &b) { b = Bool(); }
template<class S, class T> inline void _SingleInput(std::pair<S, T> &p) { _SingleInput(p.first); _SingleInput(p.second); }
template<class T> inline void _SingleInput(std::vector<T> &v) { for (T &x: v) _SingleInput(x); }

void input() { }
template<class T1, class... T2> void input(T1& t1, T2&... t2) { _SingleInput(t1); input(t2...); }

} // fastin

namespace fastout {

namespace writer {

const size_t buf_size = 1 << 18;
char buf[buf_size];
ssize_t wt = 0;

void _write() {
	write(1, buf, wt);
	wt = 0;
}

inline void wtchar(char c) {
	if (wt == buf_size - 1) [[unlikely]] {
		_write();
	}
	buf[wt++] = c;
}

template<typename T> inline void print_uint(T n) {
	if (n == 0) {
		wtchar('0');
		return;
	}
	if (wt + 20 > buf_size) _write();
	char m[19];
	int i = 18;
	for (; n > 0; i--) {
		m[i] = '0' + n % 10;
		n /= 10;
	}
	memcpy(buf + wt, m + i + 1, 18 - i);
	wt += 18 - i;
}

template<typename T> inline void print_int(T n) {
	if (n == 0) {
		wtchar('0');
		return;
	}
	if (n < 0) {
		wtchar('-');
		n = -n;
	}
	if (wt + 20 > buf_size) _write();
	char m[19];
	int i = 18;
	for (; n > 0; i--) {
		m[i] = '0' + n % 10;
		n /= 10;
	}
	memcpy(buf + wt, m + i + 1, 18 - i);
	wt += 18 - i;
}

template<typename T> inline void print_bigint(T n) {
	if (n == 0) {
		wtchar('0');
		return;
	}
	if (n < 0) {
		wtchar('-');
		n = -n;
	}
	if (wt + 40 > buf_size) _write();
	char m[39];
	int i = 38;
	for (; n > 0; i--) {
		m[i] = '0' + n % 10;
		n /= 10;
	}
	memcpy(buf + wt, m + i + 1, 38 - i);
	wt += 38 - i;
}

void print_char(char c) {
	wtchar(c);
}

void print_string(std::string s) {
	const char *c = s.c_str();
	for (int i = 0, l = s.size(); i < l; i++) {
		int j = std::min(l, i + (int)(buf_size - wt));
		memcpy(buf + wt, c + i, j - i);
		wt += j - i;
		_write();
		i = j;
	}
}

template<typename T> void print_double(T d) {
	print_string(std::to_string(d));
}

struct _writer_atexit {
	_writer_atexit() {
		atexit(_write);
	}
} _wt_atexit;

} // writer

inline void _SingleOutput(short n) { writer::print_int<short>(n); }
inline void _SingleOutput(unsigned short n) { writer::print_uint<unsigned short>(n); }
inline void _SingleOutput(int n) { writer::print_int<int>(n); }
inline void _SingleOutput(unsigned int n) { writer::print_uint<unsigned int>(n); }
inline void _SingleOutput(long n) { writer::print_int<long>(n); }
inline void _SingleOutput(unsigned long n) { writer::print_uint<unsigned long>(n); }
inline void _SingleOutput(long long n) { writer::print_int<long long>(n); }
inline void _SingleOutput(unsigned long long n) { writer::print_uint<unsigned long long>(n); }
inline void _SingleOutput(__int128_t n) { writer::print_int<__int128_t>(n); }
inline void _SingleOutput(__uint128_t n) { writer::print_uint<__uint128_t>(n); }
inline void _SingleOutput(float d) { writer::print_double<float>(d); }
inline void _SingleOutput(double d) { writer::print_double<double>(d); }
inline void _SingleOutput(long double d) { writer::print_double<long double>(d); }
inline void _SingleOutput(std::string s) { writer::print_string(s); }
inline void _SingleOutput(const char s[]) { writer::print_string(std::string(s)); }
inline void _SingleOutput(char c) { writer::wtchar(c); }
inline void _SingleOutput(bool b) { writer::wtchar(b ? '1' : '0'); }
template<class S, class T> inline void _SingleOutput(std::pair<S, T> p) { _SingleOutput(p.first); writer::wtchar(' '); _SingleOutput(p.second); }
template<class T> inline void _SingleOutput(std::vector<T> v) { for (int i = 0; i < v.size() - 1; i++) { _SingleOutput(v[i]); writer::wtchar(' '); } _SingleOutput(v.back()); }

void print() { writer::wtchar('\n'); }
template<class T1, class... T2> void print(T1 t1, T2... t2) { _SingleOutput(t1); writer::wtchar(' '); print(t2...); }

} // namespace fastout

} // namespace fastio

} // namespace hiro1729

using hiro1729::fastio::fastin::input;
using hiro1729::fastio::fastout::print;
using namespace std;

using ll = long long;

template<typename T>
struct MinSparseTable {
	T** table;
	int* logs;
	MinSparseTable(vector<T> a) {
		logs = new int[a.size() + 1];
		for (int i = 2; i <= a.size(); i++) {
			logs[i] = logs[i >> 1] + 1;
		}
		table = new T*[logs[a.size()] + 1];
		table[0] = new T[a.size()];
		for (int j = 0; j < a.size(); j++) {
			table[0][j] = a[j];
		}
		for (int i = 1; i <= logs[a.size()]; i++) {
			table[i] = new T[a.size() - (1 << i) + 1];
			for (int j = 0; j <= a.size() - (1 << i); j++) {
				table[i][j] = table[i - 1][j] < table[i - 1][j + (1 << (i - 1))] ? table[i - 1][j] : table[i - 1][j + (1 << (i - 1))];
			}
		}
	}
	T query(int l, int r) {
		int t = logs[r - l];
		return table[t][l] < table[t][r - (1 << t)] ? table[t][l] : table[t][r - (1 << t)];
	}
};

template<typename T>
struct MaxSparseTable {
	T** table;
	int* logs;
	MaxSparseTable(vector<T> a) {
		logs = new int[a.size() + 1];
		for (int i = 2; i <= a.size(); i++) {
			logs[i] = logs[i >> 1] + 1;
		}
		table = new T*[logs[a.size()] + 1];
		table[0] = new T[a.size()];
		for (int j = 0; j < a.size(); j++) {
			table[0][j] = a[j];
		}
		for (int i = 1; i <= logs[a.size()]; i++) {
			table[i] = new T[a.size() - (1 << i) + 1];
			for (int j = 0; j <= a.size() - (1 << i); j++) {
				table[i][j] = table[i - 1][j] > table[i - 1][j + (1 << (i - 1))] ? table[i - 1][j] : table[i - 1][j + (1 << (i - 1))];
			}
		}
	}
	T query(int l, int r) {
		int t = logs[r - l];
		return table[t][l] > table[t][r - (1 << t)] ? table[t][l] : table[t][r - (1 << t)];
	}
};

int main() {
	int N, Q, S, L, R;
	ll A, B, D;
	input(N);
	vector<ll> amin(N), amax(N), bmin(N), bmax(N), cmin(N), cmax(N);
	for (int i = 0; i < N; i++) {
		input(A, B, D);
		amin[i] = B - D;
		amax[i] = B;
		bmin[i] = A + B - 2 * D;
		bmax[i] = A + B;
		cmin[i] = A - B;
		cmax[i] = A - B + 2 * D;
	}
	input(Q);
	MaxSparseTable<ll> as(amin), bs(bmin), cs(cmin);
	MinSparseTable<ll> As(amax), Bs(bmax), Cs(cmax);
	while (Q--) {
		input(S, L, R);
		S--;
		L--;
		if ((amin[S] < As.query(L, R) && as.query(L, R) < amax[S]) && (bmin[S] < Bs.query(L, R) && bs.query(L, R) < bmax[S]) && (cmin[S] < Cs.query(L, R) && cs.query(L, R) < cmax[S])) {
			print("Yes");
		} else {
			print("No");
		}
	}
}

yukicoder

結果

テストケース

ソースコード