General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
114142853 Practice:
ecnerwala
1517H - 38 C++17 (GCC 9-64) Hacked 327 ms 9416 KB 2021-04-24 21:39:16 2021-04-24 21:39:16
→ Source
#include <bits/stdc++.h>

template <typename T> void setmax(T& a, T b) { if (b > a) a = b; }
template <typename T> void setmin(T& a, T b) { if (b < a) a = b; }

template <typename T> struct range_val {
	T lo, hi;
	range_val() : lo(), hi( ){}
	range_val(T lo_, T hi_) : lo(lo_), hi(hi_) {}

	friend std::istream& operator >> (std::istream& i, range_val& v) { return i >> v.lo >> v.hi; }
	friend std::ostream& operator << (std::ostream& o, range_val v) { return o << v.lo << '-' << v.hi; }

	friend bool operator == (range_val a, range_val b) { return a.lo == b.lo && a.hi == b.hi; }

	explicit operator bool() const { return lo <= hi; }

	range_val operator + () const { return range_val(lo, hi); }
	range_val operator - () const { return range_val(-hi, -lo); }
	friend range_val operator + (range_val a, range_val b) { return range_val(a.lo + b.lo, a.hi + b.hi); }
	friend range_val operator - (range_val a, range_val b) { return a + (-b); }

	range_val& operator &= (const range_val& o) { setmax(lo, o.lo); setmin(hi, o.hi); return *this; }
	friend range_val operator & (range_val a, range_val b) { return range_val(max(a.lo, b.lo), min(a.hi, b.hi)); }
};

int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);

	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		vector<range_val<int64_t>> X(N); for (auto& a : X) cin >> a;
		vector<range_val<int64_t>> Y(N-1); for (auto& a : Y) cin >> a;
		vector<range_val<int64_t>> Z(N-2); for (auto& a : Z) cin >> a;
		cout << ([&]() -> bool {
			for (int z = 0; true; z++) {
				if (z > 60) return false;
				auto old_X = X;
				auto old_Y = Y;
				auto old_Z = Z;
				for (int i = 0; i < N-2; i++) {
					Y[i+1] &= Y[i] + Z[i];
				}
				for (int i = N-3; i >= 0; i--) {
					Y[i] &= Y[i+1] - Z[i];
				}

				for (int i = 0; i < N-1; i++) {
					X[i+1] &= X[i] + Y[i];
				}
				for (int i = N-2; i >= 0; i--) {
					X[i] &= X[i+1] - Y[i];
				}

				for (int i = 0; i < N-1; i++) {
					Y[i] &= X[i+1] - X[i];
				}

				for (int i = 0; i < N-2; i++) {
					Z[i] &= Y[i+1] - Y[i];
				}

				if (X == old_X && Y == old_Y && Z == old_Z) break;

				for (auto& v : X) if (!v) return false;
				for (auto& v : Y) if (!v) return false;
				for (auto& v : Z) if (!v) return false;
			}

			return true;
		}() ? "YES" : "NO") << '\n';
	}

	return 0;
}

// LP duality means that we just need to check if there's a negative cycle

// -A0 + 2A1 - A2
//       -A1 +2A2 - A3
//  A0         A2   A3
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details