結果
| 問題 | No.2885 Range Triangle Collision Decision Queries |
| ユーザー |
 sortA0329
|
| 提出日時 | 2024-09-07 20:52:58 |
| 言語 | C++23(gcc13) (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 64 ms / 3,000 ms |
| コード長 | 36,842 bytes |
| コンパイル時間 | 2,167 ms |
| コンパイル使用メモリ | 90,704 KB |
| 実行使用メモリ | 54,288 KB |
| 最終ジャッジ日時 | 2024-09-07 20:53:11 |
| 合計ジャッジ時間 | 13,075 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 9 ms
6,812 KB |
| testcase_01 | AC | 9 ms
6,944 KB |
| testcase_02 | AC | 9 ms
6,940 KB |
| testcase_03 | AC | 9 ms
6,944 KB |
| testcase_04 | AC | 9 ms
6,944 KB |
| testcase_05 | AC | 59 ms
45,324 KB |
| testcase_06 | AC | 58 ms
45,204 KB |
| testcase_07 | AC | 56 ms
45,328 KB |
| testcase_08 | AC | 57 ms
45,324 KB |
| testcase_09 | AC | 57 ms
45,324 KB |
| testcase_10 | AC | 61 ms
53,776 KB |
| testcase_11 | AC | 61 ms
54,028 KB |
| testcase_12 | AC | 61 ms
53,904 KB |
| testcase_13 | AC | 59 ms
53,900 KB |
| testcase_14 | AC | 60 ms
53,780 KB |
| testcase_15 | AC | 61 ms
50,960 KB |
| testcase_16 | AC | 60 ms
51,088 KB |
| testcase_17 | AC | 49 ms
50,188 KB |
| testcase_18 | AC | 58 ms
51,728 KB |
| testcase_19 | AC | 57 ms
51,856 KB |
| testcase_20 | AC | 57 ms
51,984 KB |
| testcase_21 | AC | 56 ms
51,344 KB |
| testcase_22 | AC | 34 ms
51,468 KB |
| testcase_23 | AC | 59 ms
51,216 KB |
| testcase_24 | AC | 58 ms
51,216 KB |
| testcase_25 | AC | 46 ms
50,704 KB |
| testcase_26 | AC | 60 ms
54,160 KB |
| testcase_27 | AC | 64 ms
54,036 KB |
| testcase_28 | AC | 62 ms
54,160 KB |
| testcase_29 | AC | 61 ms
53,904 KB |
| testcase_30 | AC | 59 ms
54,028 KB |
| testcase_31 | AC | 60 ms
54,288 KB |
| testcase_32 | AC | 62 ms
54,160 KB |
| testcase_33 | AC | 59 ms
54,032 KB |
| testcase_34 | AC | 58 ms
53,900 KB |
| testcase_35 | AC | 59 ms
53,904 KB |
| testcase_36 | AC | 57 ms
53,904 KB |
| testcase_37 | AC | 57 ms
54,284 KB |
| testcase_38 | AC | 56 ms
53,904 KB |
| testcase_39 | AC | 62 ms
54,164 KB |
| testcase_40 | AC | 62 ms
53,904 KB |
| testcase_41 | AC | 57 ms
53,908 KB |
| testcase_42 | AC | 58 ms
53,904 KB |
| testcase_43 | AC | 56 ms
50,572 KB |
| testcase_44 | AC | 53 ms
45,964 KB |
| testcase_45 | AC | 59 ms
50,768 KB |
| testcase_46 | AC | 59 ms
50,764 KB |
| testcase_47 | AC | 59 ms
52,496 KB |
| testcase_48 | AC | 59 ms
52,240 KB |
| testcase_49 | AC | 8 ms
6,944 KB |
| testcase_50 | AC | 9 ms
6,944 KB |
| testcase_51 | AC | 10 ms
6,940 KB |
| testcase_52 | AC | 10 ms
6,940 KB |
| testcase_53 | AC | 2 ms
6,940 KB |
| testcase_54 | AC | 2 ms
6,944 KB |
ソースコード
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#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; }
};
}
// https://judge.yosupo.jp/submission/217135
using idt=std::size_t;
template<class _Tp>
struct _Sprod{
_Tp*f;
idt n;
_Sprod():f(nullptr),n(0){}
void build(idt _n,auto&&fn){
delete []f;
f=new _Tp[(_n<2?1:(std::__lg(_n-1)+1))*_n];
n=_n;
for(idt i=0;i<n;++i){
f[i]=fn(i);
}
for(idt j=2,w=1;j<n;j<<=1,++w){
auto t=f+w*n;
for(idt i=0;i+j<n;i+=2*j){
t[i+j-1]=f[i+j-1],t[i+j]=f[i+j];
for(idt k=i+j-1;k>i;--k){
t[k-1]=f[k-1]*t[k];
}
idt ed=std::min(n,i+j+j)-1;
for(idt k=i+j;k<ed;++k){
t[k+1]=t[k]*f[k+1];
}
}
}
}
~_Sprod(){
delete []f;
}
_Tp get(idt l,idt r)const{
if(l==r){
return f[l];
}
auto t=f+(63^__builtin_clzll(l^r))*n;
return t[l]*t[r];
}
};
template<class _Tp,idt _Bk=16>
struct RangeProd{
_Tp*arr,*pre,*suf;
idt n;
_Sprod<_Tp> spd;
RangeProd(idt _n,auto&&fn):arr(new _Tp[_n]),pre(new _Tp[_n]),suf(new _Tp[_n]),n(_n){
for(idt i=0;i<n;++i){
arr[i]=fn(i);
}
for(idt i=0;i<n;i+=_Bk){
pre[i]=arr[i];
for(idt j=i+1,ed=std::min(n,i+_Bk);j<ed;++j){
pre[j]=pre[j-1]*arr[j];
}
}
for(idt i=0;i<n;i+=_Bk){
idt ed=std::min(n,i+_Bk);
suf[ed-1]=arr[ed-1];
for(idt j=ed-1;j!=i;--j){
suf[j-1]=arr[j-1]*suf[j];
}
}
if(n>_Bk){
spd.build(n/_Bk,[&](idt i){
return suf[i*_Bk];
});
}
}
~RangeProd(){
delete []arr;
delete []pre;
delete []suf;
}
_Tp get(idt l,idt r)const{
idt bl=l/_Bk,br=r/_Bk;
if(bl==br){
_Tp res=arr[l];
for(idt i=l+1;i<=r;++i){
res=res*arr[i];
}
return res;
}
if(bl+1==br){
return suf[l]*pre[r];
}
return suf[l]*spd.get(bl+1,br-1)*pre[r];
}
};
struct Data {
long long l1, l2, l3, r1, r2, r3;
Data operator*(Data b) const {
return { max(l1, b.l1), max(l2, b.l2), max(l3, b.l3), min(r1, b.r1), min(r2, b.r2), min(r3, b.r3) };
}
};
char outbuf[800064];
using namespace gsh;
using namespace gsh::itype;
MmapReader r;
int main() {
u32 N = Parser<u8dig>{}(r);
RangeProd<Data> st(N, [](idt i) -> Data {
long long A = Parser<i64>{}(r), B = Parser<i64>{}(r), D = Parser<i64>{}(r);
return { B - D, (A - D) + (B - D), A - B, B, A + B, (A + D) - (B - D) };
});
u32 Q = Parser<u8dig>{}(r);
char* out = outbuf;
while(Q--) {
int S = Parser<u8dig>{}(r), L = Parser<u8dig>{}(r), R = Parser<u8dig>{}(r);
auto [l1, l2, l3, r1, r2, r3] = st.arr[S - 1];
auto [sl1, sl2, sl3, sr1, sr2, sr3] = st.get(L - 1, R - 1);
const bool f = l1 < sr1 && sl1 < r1 && l2 < sr2 && sl2 < r2 && l3 < sr3 && sl3 < r3;
memcpy(out, f ? "Yes\n" : "No\n\0", 4);
out += 3 + f;
}
write(1, outbuf, out - outbuf);
}