結果
| 問題 |
No.2885 Range Triangle Collision Decision Queries
|
| コンテスト | |
| ユーザー |
 Rac
|
| 提出日時 | 2024-09-08 08:58:16 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 36,890 bytes |
| コンパイル時間 | 8,694 ms |
| コンパイル使用メモリ | 315,772 KB |
| 実行使用メモリ | 26,128 KB |
| 最終ジャッジ日時 | 2024-09-08 09:01:18 |
| 合計ジャッジ時間 | 177,641 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 36 WA * 15 TLE * 2 |
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <numeric>
#include <algorithm>
using namespace std;
#include <bit>
#include <cstdlib>
#include <cstring>
#if __has_include(<unistd.h>)
#include <unistd.h>
#endif
#ifndef _WIN32
#include <sys/mman.h>
#include <sys/stat.h>
#endif
namespace gsh {
namespace itype {
using i8 = signed char;
using u8 = unsigned char;
using i16 = short;
using u16 = unsigned short;
using i32 = int;
using u32 = unsigned;
using ilong = long;
using ulong = unsigned long;
using i64 = long long;
using u64 = unsigned long long;
#ifdef __SIZEOF_INT128__
using i128 = __int128_t;
using u128 = __uint128_t;
#endif
using isize = i32;
using usize = u32;
}
namespace ftype {
using f32 = float;
using f64 = double;
#ifdef __SIZEOF_FLOAT128__
using f128 = __float128;
#endif
using flong = long double;
}
namespace ctype {
using c8 = char;
using wc = wchar_t;
using utf8 = char8_t;
using utf16 = char16_t;
using utf32 = char32_t;
}
namespace internal {
template<class T, class U> constexpr bool IsSame = false;
template<class T> constexpr bool IsSame<T, T> = true;
template<class T, class U, class... V> constexpr bool IsSameAny = IsSame<T, U> || IsSameAny<T, V...>;
template<class T, class U> constexpr bool IsSameAny<T, U> = IsSame<T, U>;
}
namespace simd {
#if defined __GNUC__
using i8x32 = __attribute__((vector_size(32))) itype::i8;
using u8x32 = __attribute__((vector_size(32))) itype::u8;
using i16x16 = __attribute__((vector_size(32))) itype::i16;
using u16x16 = __attribute__((vector_size(32))) itype::u16;
using i32x8 = __attribute__((vector_size(32))) itype::i32;
using u32x8 = __attribute__((vector_size(32))) itype::u32;
using i64x4 = __attribute__((vector_size(32))) itype::i64;
using u64x4 = __attribute__((vector_size(32))) itype::u64;
using f32x8 = __attribute__((vector_size(32))) ftype::f32;
using f64x4 = __attribute__((vector_size(32))) ftype::f64;
using i8x64 = __attribute__((vector_size(64))) itype::i8;
using u8x64 = __attribute__((vector_size(64))) itype::u8;
using i16x32 = __attribute__((vector_size(64))) itype::i16;
using u16x32 = __attribute__((vector_size(64))) itype::u16;
using i32x16 = __attribute__((vector_size(64))) itype::i32;
using u32x16 = __attribute__((vector_size(64))) itype::u32;
using i64x8 = __attribute__((vector_size(64))) itype::i64;
using u64x8 = __attribute__((vector_size(64))) itype::u64;
using f32x16 = __attribute__((vector_size(64))) ftype::f32;
using f64x8 = __attribute__((vector_size(64))) ftype::f64;
template<class T, class U> constexpr T VectorCast(U x) {
return __builtin_convertvector(x, T);
}
template<class T> concept Is256BitVector = internal::IsSameAny<T, i8x32, i16x16, i32x8, i64x4, u8x32, u16x16, u32x8, u64x4, f32x8, f64x4>;
template<class T> concept Is512BitVector = internal::IsSameAny<T, i8x64, i16x32, i32x16, i64x8, u8x64, u16x32, u32x16, u64x8, f32x16, f64x8>;
template<class T> concept IsVector = Is256BitVector<T> || Is512BitVector<T>;
#endif
}
}
#define GSH_INTERNAL_SELECT1(a, ...) a
#define GSH_INTERNAL_SELECT2(a, b, ...) b
#define GSH_INTERNAL_SELECT3(a, b, c, ...) c
#define GSH_INTERNAL_SELECT4(a, b, c, d, ...) d
#define GSH_INTERNAL_SELECT5(a, b, c, d, e, ...) e
#define GSH_INTERNAL_SELECT6(a, b, c, d, e, f, ...) f
#define GSH_INTERNAL_SELECT7(a, b, c, d, e, f, g, ...) g
#define GSH_INTERNAL_SELECT8(a, b, c, d, e, f, g, h, ...) h
#define GSH_INTERNAL_STR(s) #s
#define GSH_INTERNAL_CONCAT(a, b) a##b
#define GSH_INTERNAL_VA_SIZE(...) GSH_INTERNAL_SELECT8(__VA_ARGS__, 7, 6, 5, 4, 3, 2, 1, 0)
#if defined __clang__ || defined __INTEL_COMPILER
#define GSH_INTERNAL_UNROLL(n) _Pragma(GSH_INTERNAL_STR(unroll n))
#elif defined __GNUC__
#define GSH_INTERNAL_UNROLL(n) _Pragma(GSH_INTERNAL_STR(GCC unroll n))
#else
#define GSH_INTERNAL_UNROLL(n)
#endif
#ifdef __GNUC__
#define GSH_INTERNAL_INLINE [[gnu::always_inline]]
#define GSH_INTERNAL_NOINLINE [[gnu::noinline]]
#elif defined _MSC_VER
#define GSH_INTERNAL_INLINE [[msvc::forceinline]]
#define GSH_INTERNAL_NOINLINE [[msvc::noinline]]
#else
#define GSH_INTERNAL_INLINE
#define GSH_INTERNAL_NOINLINE
#endif
#ifdef __GNUC__
#define GSH_INTERNAL_RESTRICT __restrict__
#elif defined _MSC_VER
#define GSH_INTERNAL_RESTRICT __restrict
#else
#define GSH_INTERNAL_RESTRICT
#endif
#ifdef __clang__
#define GSH_INTERNAL_PUSH_ATTRIBUTE(apply, ...) _Pragma(GSH_INTERNAL_STR(clang attribute push(__attribute__((__VA_ARGS__)), apply_to = apply)))
#define GSH_INTERNAL_POP_ATTRIBUTE _Pragma("clang attribute pop")
#elif defined __GNUC__
#define GSH_INTERNAL_PUSH_ATTRIBUTE(apply, ...) _Pragma("GCC push_options") _Pragma(GSH_INTERNAL_STR(GCC __VA_ARGS__))
#define GSH_INTERNAL_POP_ATTRIBUTE _Pragma("GCC pop_options")
#else
#define GSH_INTERNAL_PUSH_ATTRIBUTE(apply, ...)
#define GSH_INTERNAL_POP_ATTRIBUTE
#endif
namespace gsh {
namespace itype {
struct i4dig {};
struct u4dig {};
struct i8dig {};
struct u8dig {};
struct i16dig {};
struct u16dig {};
}
template<class T> class Parser;
namespace internal {
template<class Stream> constexpr itype::u8 Parseu8(Stream& stream) {
itype::u32 v;
std::memcpy(&v, stream.current(), 4);
v ^= 0x30303030;
itype::i32 tmp = std::countr_zero(v & 0xf0f0f0f0) >> 3;
v <<= (32 - (tmp << 3));
v = (v * 10 + (v >> 8)) & 0x00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff;
stream.skip(tmp + 1);
return v;
}
template<class Stream> constexpr itype::u16 Parseu16(Stream& stream) {
itype::u64 v;
std::memcpy(&v, stream.current(), 8);
v ^= 0x3030303030303030;
itype::i32 tmp = std::countr_zero(v & 0xf0f0f0f0f0f0f0f0) >> 3;
v <<= (64 - (tmp << 3));
v = (v * 10 + (v >> 8)) & 0x00ff00ff00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff0000ffff;
v = (v * 10000 + (v >> 32)) & 0x00000000ffffffff;
stream.skip(tmp + 1);
return v;
}
template<class Stream> constexpr itype::u32 Parseu32(Stream& stream) {
itype::u32 res = 0;
{
itype::u64 v;
std::memcpy(&v, stream.current(), 8);
if (!((v ^= 0x3030303030303030) & 0xf0f0f0f0f0f0f0f0)) {
v = (v * 10 + (v >> 8)) & 0x00ff00ff00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff0000ffff;
v = (v * 10000 + (v >> 32)) & 0x00000000ffffffff;
res = v;
stream.skip(8);
}
}
itype::u64 buf;
std::memcpy(&buf, stream.current(), 8);
{
itype::u32 v = buf;
if (!((v ^= 0x30303030) & 0xf0f0f0f0)) {
buf >>= 32;
v = (v * 10 + (v >> 8)) & 0x00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff;
res = 10000 * res + v;
stream.skip(4);
}
}
{
itype::u16 v = buf;
if (!((v ^= 0x3030) & 0xf0f0)) {
buf >>= 16;
v = (v * 10 + (v >> 8)) & 0x00ff;
res = 100 * res + v;
stream.skip(2);
}
}
{
const ctype::c8 v = ctype::c8(buf) ^ 0x30;
const bool f = !(v & 0xf0);
res = f ? 10 * res + v : res;
stream.skip(f + 1);
}
return res;
};
template<class Stream> constexpr itype::u64 Parseu64(Stream& stream) {
itype::u64 res = 0;
{
itype::u64 v;
std::memcpy(&v, stream.current(), 8);
if (!((v ^= 0x3030303030303030) & 0xf0f0f0f0f0f0f0f0)) {
stream.skip(8);
itype::u64 u;
std::memcpy(&u, stream.current(), 8);
if (!((u ^= 0x3030303030303030) & 0xf0f0f0f0f0f0f0f0)) {
v = (v * 10 + (v >> 8)) & 0x00ff00ff00ff00ff;
u = (u * 10 + (u >> 8)) & 0x00ff00ff00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff0000ffff;
u = (u * 100 + (u >> 16)) & 0x0000ffff0000ffff;
v = (v * 10000 + (v >> 32)) & 0x00000000ffffffff;
u = (u * 10000 + (u >> 32)) & 0x00000000ffffffff;
res = v * 100000000 + u;
stream.skip(8);
} else {
v = (v * 10 + (v >> 8)) & 0x00ff00ff00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff0000ffff;
v = (v * 10000 + (v >> 32)) & 0x00000000ffffffff;
res = v;
}
}
}
itype::u64 buf;
std::memcpy(&buf, stream.current(), 8);
{
itype::u32 v = buf;
if (!((v ^= 0x30303030) & 0xf0f0f0f0)) {
buf >>= 32;
v = (v * 10 + (v >> 8)) & 0x00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff;
res = 10000 * res + v;
stream.skip(4);
}
}
{
itype::u16 v = buf;
if (!((v ^= 0x3030) & 0xf0f0)) {
buf >>= 16;
v = (v * 10 + (v >> 8)) & 0x00ff;
res = 100 * res + v;
stream.skip(2);
}
}
{
const ctype::c8 v = ctype::c8(buf) ^ 0x30;
const bool f = !(v & 0xf0);
res = f ? 10 * res + v : res;
stream.skip(f + 1);
}
return res;
}
template<class Stream> constexpr itype::u128 Parseu128(Stream& stream) {
itype::u128 res = 0;
GSH_INTERNAL_UNROLL(4)
for (itype::u32 i = 0; i != 4; ++i) {
itype::u64 v;
std::memcpy(&v, stream.current(), 8);
if (((v ^= 0x3030303030303030) & 0xf0f0f0f0f0f0f0f0) != 0) break;
v = (v * 10 + (v >> 8)) & 0x00ff00ff00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff0000ffff;
v = (v * 10000 + (v >> 32)) & 0x00000000ffffffff;
if (i == 0) res = v;
else res = res * 100000000 + v;
stream.skip(8);
}
itype::u64 buf;
std::memcpy(&buf, stream.current(), 8);
itype::u64 res2 = 0, pw = 1;
{
itype::u32 v = buf;
if (!((v ^= 0x30303030) & 0xf0f0f0f0)) {
buf >>= 32;
v = (v * 10 + (v >> 8)) & 0x00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff;
res2 = v;
pw = 10000;
stream.skip(4);
}
}
{
itype::u16 v = buf;
if (!((v ^= 0x3030) & 0xf0f0)) {
buf >>= 16;
v = (v * 10 + (v >> 8)) & 0x00ff;
res2 = res2 * 100 + v;
pw *= 100;
stream.skip(2);
}
}
{
const ctype::c8 v = ctype::c8(buf) ^ 0x30;
const bool f = (v & 0xf0) == 0;
const volatile auto tmp1 = pw * 10, tmp2 = res2 * 10 + v;
const auto tmp3 = tmp1, tmp4 = tmp2;
pw = f ? tmp3 : pw;
res2 = f ? tmp4 : res2;
stream.skip(f + 1);
}
return res * pw + res2;
}
template<class Stream> constexpr itype::u16 Parseu4dig(Stream& stream) {
itype::u32 v;
std::memcpy(&v, stream.current(), 4);
v ^= 0x30303030;
itype::i32 tmp = std::countr_zero(v & 0xf0f0f0f0) >> 3;
v <<= (32 - (tmp << 3));
v = (v * 10 + (v >> 8)) & 0x00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff;
stream.skip(tmp + 1);
return v;
}
template<class Stream> constexpr itype::u32 Parseu8dig(Stream& stream) {
itype::u64 v;
std::memcpy(&v, stream.current(), 8);
v ^= 0x3030303030303030;
const itype::u64 msk = v & 0xf0f0f0f0f0f0f0f0;
itype::i32 tmp = std::countr_zero(msk) >> 3;
v <<= (64 - (tmp << 3));
v = (v * 10 + (v >> 8)) & 0x00ff00ff00ff00ff;
v = (v * 100 + (v >> 16)) & 0x0000ffff0000ffff;
v = (v * 10000 + (v >> 32)) & 0x00000000ffffffff;
stream.skip(tmp + 1);
return v;
}
}
template<> class Parser<itype::u8> {
public:
template<class Stream> constexpr itype::u8 operator()(Stream& stream) const {
stream.reload(8);
return internal::Parseu8(stream);
}
};
template<> class Parser<itype::i8> {
public:
template<class Stream> constexpr itype::i8 operator()(Stream& stream) const {
stream.reload(8);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i8 tmp = internal::Parseu8(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<itype::u16> {
public:
template<class Stream> constexpr itype::u16 operator()(Stream& stream) const {
stream.reload(8);
return internal::Parseu16(stream);
}
};
template<> class Parser<itype::i16> {
public:
template<class Stream> constexpr itype::i16 operator()(Stream& stream) const {
stream.reload(8);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i16 tmp = internal::Parseu16(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<itype::u32> {
public:
template<class Stream> constexpr itype::u32 operator()(Stream& stream) const {
stream.reload(16);
return internal::Parseu32(stream);
}
};
template<> class Parser<itype::i32> {
public:
template<class Stream> constexpr itype::i32 operator()(Stream& stream) const {
stream.reload(16);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i32 tmp = internal::Parseu32(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<itype::u64> {
public:
template<class Stream> constexpr itype::u64 operator()(Stream& stream) const {
stream.reload(32);
return internal::Parseu64(stream);
}
};
template<> class Parser<itype::i64> {
public:
template<class Stream> constexpr itype::i64 operator()(Stream& stream) const {
stream.reload(32);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i64 tmp = internal::Parseu64(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<itype::u128> {
public:
template<class Stream> constexpr itype::u128 operator()(Stream& stream) const {
stream.reload(64);
return internal::Parseu128(stream);
}
};
template<> class Parser<itype::i128> {
public:
template<class Stream> constexpr itype::i128 operator()(Stream& stream) const {
stream.reload(64);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i128 tmp = internal::Parseu128(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<itype::u4dig> {
public:
template<class Stream> constexpr itype::u16 operator()(Stream& stream) const {
stream.reload(8);
return internal::Parseu4dig(stream);
}
};
template<> class Parser<itype::i4dig> {
public:
template<class Stream> constexpr itype::i16 operator()(Stream& stream) const {
stream.reload(8);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i16 tmp = internal::Parseu4dig(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<itype::u8dig> {
public:
template<class Stream> constexpr itype::u32 operator()(Stream& stream) const {
stream.reload(16);
return internal::Parseu8dig(stream);
}
};
template<> class Parser<itype::i8dig> {
public:
template<class Stream> constexpr itype::i32 operator()(Stream& stream) const {
stream.reload(16);
bool neg = *stream.current() == '-';
stream.skip(neg);
itype::i32 tmp = internal::Parseu8dig(stream);
if (neg) tmp = -tmp;
return tmp;
}
};
template<> class Parser<ctype::c8> {
public:
template<class Stream> constexpr ctype::c8 operator()(Stream& stream) const {
stream.reload(2);
ctype::c8 tmp = *stream.current();
stream.skip(2);
return tmp;
}
};
template<> class Parser<ctype::c8*> {
ctype::c8* s;
itype::u32 n;
public:
constexpr Parser(ctype::c8* s_, itype::u32 n_ = 0xffffffff) noexcept : s(s_), n(n_) {}
template<class Stream> constexpr void operator()(Stream& stream) const {
if (n == 0xffffffff) {
stream.reload(16);
ctype::c8* c = s;
while (true) {
const ctype::c8* e = stream.current();
while (*e >= '!') ++e;
const itype::u32 len = e - stream.current();
std::memcpy(c, stream.current(), len);
stream.skip(len);
c += len;
if (stream.avail() == 0) stream.reload();
else break;
}
stream.skip(1);
*c = '\0';
} else {
itype::u32 rem = n;
ctype::c8* c = s;
itype::u32 avail = stream.avail();
while (avail <= rem) {
std::memcpy(c, stream.current(), avail);
c += avail;
rem -= avail;
stream.skip(avail);
stream.reload();
avail = stream.avail();
}
std::memcpy(c, stream.current(), rem);
c += rem;
stream.skip(rem + 1);
*c = '\0';
}
}
};
template<class T> class Formatter;
namespace internal {
template<itype::u32> constexpr auto InttoStr = [] {
struct {
ctype::c8 table[40004] = {};
} res;
for (itype::u32 i = 0; i != 10000; ++i) {
res.table[4 * i + 0] = (i / 1000 + '0');
res.table[4 * i + 1] = (i / 100 % 10 + '0');
res.table[4 * i + 2] = (i / 10 % 10 + '0');
res.table[4 * i + 3] = (i % 10 + '0');
}
return res;
}();
template<class Stream> constexpr void Formatu16(Stream& stream, itype::u16 n) {
auto copy1 = [&](itype::u16 x) {
itype::u32 off = (x < 10) + (x < 100) + (x < 1000);
std::memcpy(stream.current(), InttoStr<0>.table + (4 * x + off), 4);
stream.skip(4 - off);
};
auto copy2 = [&](itype::u16 x) {
std::memcpy(stream.current(), InttoStr<0>.table + 4 * x, 4);
stream.skip(4);
};
if (n < 10000) copy1(n);
else {
copy1(n / 10000);
copy2(n % 10000);
}
}
template<class Stream> constexpr void Formatu32(Stream& stream, itype::u32 n) {
auto copy1 = [&](itype::u32 x) {
itype::u32 off = (x < 10) + (x < 100) + (x < 1000);
std::memcpy(stream.current(), InttoStr<0>.table + (4 * x + off), 4);
stream.skip(4 - off);
};
auto copy2 = [&](itype::u32 x) {
std::memcpy(stream.current(), InttoStr<0>.table + 4 * x, 4);
stream.skip(4);
};
if (n < 100000000) {
if (n < 10000) copy1(n);
else {
copy1(n / 10000);
copy2(n % 10000);
}
} else {
copy1(n / 100000000);
copy2(n / 10000 % 10000);
copy2(n % 10000);
}
}
template<class Stream> constexpr void Formatu64(Stream& stream, itype::u64 n) {
auto copy1 = [&](itype::u32 x) {
itype::u32 off = (x < 10) + (x < 100) + (x < 1000);
std::memcpy(stream.current(), InttoStr<0>.table + (4 * x + off), 4);
stream.skip(4 - off);
};
auto copy2 = [&](itype::u32 x) {
std::memcpy(stream.current(), InttoStr<0>.table + 4 * x, 4);
stream.skip(4);
};
if (n < 10000000000000000) {
if (n < 1000000000000) {
if (n < 100000000) {
if (n < 10000) copy1(n);
else {
copy1(n / 10000);
copy2(n % 10000);
}
} else {
copy1(n / 100000000);
copy2(n / 10000 % 10000);
copy2(n % 10000);
}
} else {
copy1(n / 1000000000000);
copy2(n / 100000000 % 10000);
copy2(n / 10000 % 10000);
copy2(n % 10000);
}
} else {
copy1(n / 10000000000000000);
copy2(n / 1000000000000 % 10000);
copy2(n / 100000000 % 10000);
copy2(n / 10000 % 10000);
copy2(n % 10000);
}
}
template<class Stream> constexpr void Formatu128(Stream& stream, itype::u128 n) {
auto copy1 = [&](itype::u32 x) {
itype::u32 off = (x < 10) + (x < 100) + (x < 1000);
std::memcpy(stream.current(), InttoStr<0>.table + (4 * x + off), 4);
stream.skip(4 - off);
};
auto copy2 = [&](itype::u32 x) {
std::memcpy(stream.current(), InttoStr<0>.table + 4 * x, 4);
stream.skip(4);
};
auto div_1e16 = [&](itype::u64& rem) -> itype::u64 {
if (std::is_constant_evaluated()) {
rem = n % 10000000000000000;
return n / 10000000000000000;
}
itype::u64 res;
__asm__("divq %[v]" : "=a"(res), "=d"(rem) : [v] "r"(10000000000000000), "a"(static_cast<itype::u64>(n)), "d"(static_cast<itype::u64>(n >> 64)));
return res;
};
constexpr itype::u128 t = static_cast<itype::u128>(10000000000000000) * 10000000000000000;
if (n >= t) {
const itype::u32 dv = n / t;
n -= dv * t;
if (dv >= 10000) {
copy1(dv / 10000);
copy2(dv % 10000);
} else copy1(dv);
itype::u64 a, b = 0;
a = div_1e16(b);
const itype::u32 c = a / 100000000, d = a % 100000000, e = b / 100000000, f = b % 100000000;
copy2(c / 10000), copy2(c % 10000);
copy2(d / 10000), copy2(d % 10000);
copy2(e / 10000), copy2(e % 10000);
copy2(f / 10000), copy2(f % 10000);
} else {
itype::u64 a, b = 0;
a = div_1e16(b);
const itype::u32 c = a / 100000000, d = a % 100000000, e = b / 100000000, f = b % 100000000;
const itype::u32 g = c / 10000, h = c % 10000, i = d / 10000, j = d % 10000, k = e / 10000, l = e % 10000, m = f / 10000, n = f % 10000;
if (a == 0) {
if (e == 0) {
if (m == 0) copy1(n);
else copy1(m), copy2(n);
} else {
if (k == 0) copy1(l), copy2(m), copy2(n);
else copy1(k), copy2(l), copy2(m), copy2(n);
}
} else {
if (c == 0) {
if (i == 0) copy1(j), copy2(k), copy2(l), copy2(m), copy2(n);
else copy1(i), copy2(j), copy2(k), copy2(l), copy2(m), copy2(n);
} else {
if (g == 0) copy1(h), copy2(i), copy2(j), copy2(k), copy2(l), copy2(m), copy2(n);
else copy1(g), copy2(h), copy2(i), copy2(j), copy2(k), copy2(l), copy2(m), copy2(n);
}
}
}
}
template<class Stream> constexpr void Formatu8dig(Stream& stream, itype::u32 x) {
const itype::u32 n = x;
auto copy1 = [&](itype::u32 x) {
itype::u32 off = (x < 10) + (x < 100) + (x < 1000);
std::memcpy(stream.current(), InttoStr<0>.table + (4 * x + off), 4);
stream.skip(4 - off);
};
auto copy2 = [&](itype::u32 x) {
std::memcpy(stream.current(), InttoStr<0>.table + 4 * x, 4);
stream.skip(4);
};
if (n < 10000) copy1(n);
else {
copy1(n / 10000);
copy2(n % 10000);
}
}
template<class Stream> constexpr void Formatu16dig(Stream& stream, itype::u64 x) {
const itype::u64 n = x;
auto copy1 = [&](itype::u64 x) {
itype::u32 off = (x < 10) + (x < 100) + (x < 1000);
std::memcpy(stream.current(), InttoStr<0>.table + (4 * x + off), 4);
stream.skip(4 - off);
};
auto copy2 = [&](itype::u64 x) {
std::memcpy(stream.current(), InttoStr<0>.table + 4 * x, 4);
stream.skip(4);
};
if (n < 1000000000000) {
if (n < 100000000) {
if (n < 10000) copy1(n);
else {
copy1(n / 10000);
copy2(n % 10000);
}
} else {
copy1(n / 100000000);
copy2(n / 10000 % 10000);
copy2(n % 10000);
}
} else {
copy1(n / 1000000000000);
copy2(n / 100000000 % 10000);
copy2(n / 10000 % 10000);
copy2(n % 10000);
}
}
}
template<> class Formatter<itype::u16> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::u16 n) const {
stream.reload(8);
internal::Formatu16(stream, n);
}
};
template<> class Formatter<itype::i16> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::i16 n) const {
stream.reload(8);
*stream.current() = '-';
stream.skip(n < 0);
internal::Formatu16(stream, n < 0 ? -n : n);
}
};
template<> class Formatter<itype::u32> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::u32 n) const {
stream.reload(16);
internal::Formatu32(stream, n);
}
};
template<> class Formatter<itype::i32> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::i32 n) const {
stream.reload(16);
*stream.current() = '-';
stream.skip(n < 0);
internal::Formatu32(stream, n < 0 ? -n : n);
}
};
template<> class Formatter<itype::u64> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::u64 n) const {
stream.reload(32);
internal::Formatu64(stream, n);
}
};
template<> class Formatter<itype::i64> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::i64 n) const {
stream.reload(32);
*stream.current() = '-';
stream.skip(n < 0);
internal::Formatu64(stream, n < 0 ? -n : n);
}
};
template<> class Formatter<itype::u128> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::u128 n) const {
stream.reload(64);
internal::Formatu128(stream, n);
}
};
template<> class Formatter<itype::i128> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::i128 n) const {
stream.reload(64);
*stream.current() = '-';
stream.skip(n < 0);
internal::Formatu128(stream, n < 0 ? -n : n);
}
};
template<> class Formatter<itype::u8dig> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::u32 n) const {
stream.reload(8);
internal::Formatu8dig(stream, n);
}
};
template<> class Formatter<itype::i8dig> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::i32 n) const {
stream.reload(9);
*stream.current() = '-';
stream.skip(n < 0);
internal::Formatu8dig(stream, static_cast<itype::u32>(n < 0 ? -n : n));
}
};
template<> class Formatter<itype::u16dig> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::u64 n) const {
stream.reload(16);
internal::Formatu16dig(stream, n);
}
};
template<> class Formatter<itype::i16dig> {
public:
template<class Stream> constexpr void operator()(Stream& stream, itype::i64 n) const {
stream.reload(17);
*stream.current() = '-';
stream.skip(n < 0);
internal::Formatu16dig(stream, static_cast<itype::u64>(n < 0 ? -n : n));
}
};
template<> class Formatter<ctype::c8> {
public:
template<class Stream> constexpr void operator()(Stream& stream, ctype::c8 c) const {
stream.reload(1);
*stream.current() = c;
stream.skip(1);
}
};
template<> class Formatter<const ctype::c8*> {
public:
template<class Stream> constexpr void operator()(Stream& stream, const ctype::c8* s) const {
itype::u32 len = std::strlen(s);
itype::u32 avail = stream.avail();
if (avail >= len) [[likely]] {
std::memcpy(stream.current(), s, len);
stream.skip(len);
} else {
std::memcpy(stream.current(), s, avail);
len -= avail;
s += avail;
stream.skip(avail);
while (len != 0) {
stream.reload();
avail = stream.avail();
const itype::u32 tmp = len < avail ? len : avail;
std::memcpy(stream.current(), s, tmp);
len -= tmp;
s += tmp;
stream.skip(tmp);
}
}
}
};
template<itype::u32 Bufsize = (1 << 18)> class BasicReader {
itype::i32 fd = 0;
ctype::c8 buf[Bufsize + 1] = {};
ctype::c8 *cur = buf, *eof = buf;
public:
BasicReader() {}
BasicReader(itype::i32 filehandle) : fd(filehandle) {}
BasicReader(const BasicReader& rhs) {
fd = rhs.fd;
std::memcpy(buf, rhs.buf, rhs.eof - rhs.cur);
cur = buf + (rhs.cur - rhs.buf);
eof = buf + (rhs.cur - rhs.eof);
}
BasicReader& operator=(const BasicReader& rhs) {
fd = rhs.fd;
std::memcpy(buf, rhs.buf, rhs.eof - rhs.cur);
cur = buf + (rhs.cur - rhs.buf);
eof = buf + (rhs.cur - rhs.eof);
return *this;
}
void reload() {
if (eof == buf + Bufsize || eof == cur || [&] {
auto p = cur;
while (*p >= '!') ++p;
return p;
}() == eof) [[likely]] {
itype::u32 rem = eof - cur;
std::memmove(buf, cur, rem);
*(eof = buf + rem + read(fd, buf + rem, Bufsize - rem)) = '\0';
cur = buf;
}
}
void reload(itype::u32 len) {
if (avail() < len) [[unlikely]]
reload();
}
itype::u32 avail() const { return eof - cur; }
const ctype::c8* current() const { return cur; }
void skip(itype::u32 n) { cur += n; }
};
class MmapReader {
const itype::i32 fh;
ctype::c8* buf;
ctype::c8 *cur, *eof;
public:
MmapReader() : fh(0) {
#ifdef _WIN32
write(1, "gsh::MmapReader / gsh::MmapReader is not available for Windows.\n", 64);
std::exit(1);
#else
struct stat st;
fstat(0, &st);
buf = reinterpret_cast<ctype::c8*>(mmap(nullptr, st.st_size + 64, PROT_READ, MAP_PRIVATE, 0, 0));
cur = buf;
eof = buf + st.st_size;
#endif
}
void reload() const {}
void reload(itype::u32) const {}
itype::u32 avail() const { return eof - cur; }
const ctype::c8* current() const { return cur; }
void skip(itype::u32 n) { cur += n; }
};
class StaticStrReader {
const ctype::c8* cur;
public:
constexpr StaticStrReader() {}
constexpr StaticStrReader(const ctype::c8* c) : cur(c) {}
constexpr void reload() const {}
constexpr void reload(itype::u32) const {}
constexpr itype::u32 avail() const { return static_cast<itype::u32>(-1); }
constexpr const ctype::c8* current() { return cur; }
constexpr void skip(itype::u32 n) { cur += n; }
};
template<itype::u32 Bufsize = (1 << 18)> class BasicWriter {
itype::i32 fd = 1;
ctype::c8 buf[Bufsize + 1] = {};
ctype::c8 *cur = buf, *eof = buf + Bufsize;
public:
BasicWriter() {}
BasicWriter(itype::i32 filehandle) : fd(filehandle) {}
BasicWriter(const BasicWriter& rhs) {
fd = rhs.fd;
std::memcpy(buf, rhs.buf, rhs.cur - rhs.buf);
cur = buf + (rhs.cur - rhs.buf);
}
BasicWriter& operator=(const BasicWriter& rhs) {
fd = rhs.fd;
std::memcpy(buf, rhs.buf, rhs.cur - rhs.buf);
cur = buf + (rhs.cur - rhs.buf);
return *this;
}
void reload() {
[[maybe_unused]] itype::i32 tmp = write(fd, buf, cur - buf);
cur = buf;
}
void reload(itype::u32 len) {
if (eof - cur < len) [[unlikely]]
reload();
}
itype::u32 avail() const { return eof - cur; }
ctype::c8* current() { return cur; }
void skip(itype::u32 n) { cur += n; }
};
class StaticStrWriter {
ctype::c8* cur;
public:
constexpr StaticStrWriter() {}
constexpr StaticStrWriter(ctype::c8* c) : cur(c) {}
constexpr void reload() const {}
constexpr void reload(itype::u32) const {}
constexpr itype::u32 avail() const { return static_cast<itype::u32>(-1); }
constexpr ctype::c8* current() { return cur; }
constexpr void skip(itype::u32 n) { cur += n; }
};
namespace internal {
constexpr itype::u64 Splitmix(itype::u64 x) {
itype::u64 z = (x + 0x9e3779b97f4a7c15);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
return z ^ (z >> 31);
}
} // namespace internal
class Rand32 {
itype::u64 val;
public:
using result_type = itype::u32;
static constexpr itype::usize word_size = sizeof(result_type) * 8;
static constexpr result_type default_seed = 0xcafef00d;
constexpr Rand32() : Rand32(default_seed) {}
constexpr explicit Rand32(result_type value) : val(internal::Splitmix((itype::u64) value << 32 | value)) {}
constexpr result_type operator()() {
itype::u64 x = val;
const itype::i32 count = x >> 61;
val = x * 0xcafef00dd15ea5e5;
x ^= x >> 22;
return x >> (22 + count);
};
constexpr void discard(itype::u64 z) {
itype::u64 pow = 0xcafef00dd15ea5e5;
while (z != 0) {
if (z & 1) val *= pow;
z >>= 1;
pow *= pow;
}
}
static constexpr result_type max() { return 4294967295u; }
static constexpr result_type min() { return 0; }
constexpr void seed(result_type value = default_seed) { val = internal::Splitmix((itype::u64) value << 32 | value); }
friend constexpr bool operator==(Rand32 x, Rand32 y) { return x.val == y.val; }
};
template<class URBG> constexpr itype::u32 Uniform32(URBG& g, itype::u32 min, itype::u32 max) {
return static_cast<itype::u32>((static_cast<itype::u64>(g() & 4294967295u) * (max - min)) >> 32) + min;
}
}
char outbuf[800064];
using namespace gsh;
using namespace gsh::itype;
MmapReader r;
#include <bits/stdc++.h>
int main() {
u32 N = Parser<u8dig>{}(r);
vector<tuple<i64, i64, i64>> tri(N);
for(u32 i = 0; i != N; ++i) {
i64 A = Parser<i64>{}(r), B = Parser<i64>{}(r), D = Parser<i64>{}(r);
tri[i] = { A, B, D };
}
u32 Q = Parser<u8dig>{}(r);
vector<tuple<u32, u32, u32>> qr(Q);
for(u32 i=0; i!=Q; ++i) {
u32 S=Parser<u8dig>{}(r) - 1,L=Parser<u8dig>{}(r) - 1,R=Parser<u8dig>{}(r);
qr[i]={ S, L, R };
}
vector<u32> cand(Q);
iota(cand.begin(), cand.end(), 0u);
auto start_time = chrono::system_clock::now();
Rand32 engine;
vector<char> fl(Q, true);
auto det=[&](u32 s, u32 t) {
if(s==t) return true;
auto in=[](i64 a, i64 b, i64 d, i64 x, i64 y) {
return y > b - d && x + y < a + b && x - y > a - b;
};
auto [a,b,c]=tri[s];
auto [d,e,f]=tri[t];
return in(a,b,c,d,e) || in(a,b,c,d-f,e-f) || in(a,b,c,d+f,e-f) || in(d,e,f,a,b) || in(d,e,f,a-c,b-c) || in(d,e,f,a+c,b-c);
};
while(chrono::system_clock::now() - start_time < 2850ms) {
for(u32 j=0; j!=cand.size();) {
auto [s,l,r]=qr[cand[j]];
if(!det(s, Uniform32(engine, l, r))) {
fl[cand[j]]=false;
cand[j] = cand.back();
cand.pop_back();
}else ++j;
}
}
char* out = outbuf;
for(u32 j=0; j!=Q; ++j) {
const bool f = fl[j];
memcpy(out, f ? "Yes\n" : "No\n\0", 4);
out += 3 + f;
}
write(1, outbuf, out - outbuf);
}