結果

問題 No.2885 Range Triangle Collision Decision Queries
ユーザー hiro1729hiro1729
提出日時 2024-09-07 22:30:22
言語 C++23
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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");
		}
	}
}
0