/* 三角形 i に対して、 P[i][0] = Bi - Ai P[i][1] = Bi + Ai P[i][2] = (Di - Bi) * 2 とします。三角形 i の内部は、以下の条件を全て満たすものです - y <= x + P[i][0] - y <= -x + P[i][1] - 2 * y >= -P[i][2] 三角形 j との面積が正であるとは、上三つの条件をどちらも満たす(x, y) の組の面積が正であることと同値です。上二つの条件をどちらも満たす最大の y を考えると、面積が正であることは以下と同値です。 - sum_{k = 1, 2, 3}(min(P[i][k], P[j][k])) > 0 よって、j = Li, ... ,Ri に対する sum_{k = 1, 2, 3}(min(P[S][k], P[j][k])) の最小値が 0 より大きければ Yes を出力すればいいです。 最小値の最小化は、自由に選んで最小化することと同じです。 よって、min(P[S][k], P[j][k]) ではなくて、P[S][k], P[j][k] の好きな方を選ぶとして良いです。 この選び方は 8 通りあるので、その全てに対する P[j][k] の寄与を seg 木に載せれば良いです。 */ #include using namespace std; using ll=long long; const ll ILL=(1ll << 60); #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) bool yneos(bool a,bool upp=0){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;} #include using F = array; F op(F l, F r){ rep(i, 0, 8) chmin(l[i], r[i]); return l; } F e(){ F tmp; rep(i, 0, 8) tmp[i] = ILL; return tmp; } void solve(); // CYAN / FREDERIC int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; rep(i, 0, t) solve(); } void solve(){ int N; cin >> N; vector> P(N, vector(3)); atcoder::segtree seg(N); rep(i, 0, N){ ll a, b, d; cin >> a >> b >> d; P[i][0] = b - a; P[i][1] = a + b; P[i][2] = (d - b) * 2; F tmp; rep(j, 0, 8){ ll x = 0; rep(k, 0, 3) if (j & (1 << k)) x += P[i][k]; tmp[j] = x; } seg.set(i, tmp); } int Q; cin >> Q; rep(i, 0, Q){ int s, l, r; cin >> s >> l >> r; s--, l--; auto tmp = seg.prod(l, r); bool ok = 1; rep(j, 0, 8){ rep(k, 0, 3) if ((j & (1 << k)) == 0) tmp[j] += P[s][k]; if (tmp[j] <= 0) ok = 0; //cout << tmp[j] << "\n"; } yneos(ok); } }