#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 400100;
int a[N], b[N], t[N], n;
namespace FastIO {
int read() {
int x = 0, o = 1;
char ch;
while (!isdigit(ch = getchar()))
if (ch == '-') o = -1;
x = ch & 15;
while (isdigit(ch = getchar()))
x = (x << 3) + (x << 1) + (ch & 15);
return x * o;
}
} using namespace FastIO;
namespace subtask1 {
int ok, vis[N], id[N];
void dfs(int dep) {
int okok = 1;
for (int i = 1; i <= n; ++i) okok &= (a[i] == b[i]);
if (okok) {
ok = 1;
return;
}
okok = 1;
for (int i = 1; i <= n; ++i)
if (a[i] != b[i] && dep > t[i]) {
okok = 0;
break;
}
if (!okok) return;
for (int i = 1; i <= n; ++i) if (a[id[i]] != b[id[i]]) {
if (a[id[i]] > b[id[i]]) {
if (!vis[a[id[i]] - 1]) {
vis[a[id[i]]] = 0;
vis[a[id[i]] - 1] = 1;
--a[id[i]];
dfs(dep + 1);
if (ok) return;
++a[id[i]];
vis[a[id[i]]] = 1;
vis[a[id[i]] - 1] = 0;
}
} else {
if (!vis[a[id[i]] + 1]) {
vis[a[id[i]]] = 0;
vis[a[id[i]] + 1] = 1;
++a[id[i]];
dfs(dep + 1);
if (ok) return;
--a[id[i]];
vis[a[id[i]]] = 1;
vis[a[id[i]] + 1] = 0;
}
}
}
}
void solve() {
ok = 0;
n = read();
for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read(), t[i] = read();
iota(id + 1, id + n + 1, 1);
int cost = 0;
for (int i = 1; i <= n; ++i)
cost += abs(a[i] - b[i]);
if (cost > *max_element(t + 1, t + n + 1)) {
cout << "No\n";
return;
}
sort(id + 1, id + n + 1, [&](auto &l, auto &r) {
return t[l] - abs(a[l] - b[l]) < t[r] - abs(a[r] - b[r]);
});
for (int i = 0; i < 20; ++i) vis[i] = 0;
for (int i = 1; i <= n; ++i) vis[a[i]] = 1;
dfs(1);
cout << (ok ? "Yes" : "No") << '\n';
}
}
namespace subtask2 {
void solve() {
n = read();
for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read(), t[i] = read();
int cost = 0;
for (int i = 1; i <= n; ++i) cost += abs(a[i] - b[i]);
if (cost > t[1]) cout << "No\n";
else {
int ok = 1;
for (int i = 1; i <= n; ++i)
if (t[i] - abs(a[i] - b[i]) < 0) {
ok = 0;
break;
}
cout << (ok ? "Yes" : "No") << '\n';
}
}
}
namespace subtask3 {
struct Box {
int a, b, t;
bool operator<(const Box &r) const {
return t < r.t;
}
} box[N];
void solve() {
n = read();
for (int i = 1; i <= n; ++i) box[i].a = read(), box[i].b = read(), box[i].t = read();
int ok = 1;
for (int i = 1; i <= n; ++i)
if (box[i].t - abs(box[i].a - box[i].b) < 0) {
ok = 0;
break;
}
if (!ok) {
cout << "No\n";
return;
}
sort(box + 1, box + n + 1);
int tim = 0;
ok = 1;
for (int i = 1; i <= n; ++i) {
int use = abs(box[i].a - box[i].b);
tim += use;
if (tim > box[i].t) {
ok = 0;
break;
}
}
cout << (ok ? "Yes" : "No") << '\n';
}
}
namespace subtask4 {
struct segm {
int first, second, id;
segm() {
first = second = id = 0;
}
segm(int a, int b, int c) {
first = a, second = b, id = c;
}
} Seg[N];
int len[N];
struct awa {
int tim, stt;
vector<segm> todo;
vector<int> pref;
bool operator<(const awa &r) const {
return stt < r.stt;
}
} yhb[N];
void solve() {
n = read();
for (int i = 1; i <= n; ++i) a[i] = read(), b[i] = read(), t[i] = read();
for (int i = 1; i <= n; ++i) {
int x = a[i], y = b[i];
if (x > y) x ^= y ^= x ^= y;
Seg[i] = {x, y, i};
}
sort(Seg + 1, Seg + n + 1, [&](auto &l, auto &r) {
return l.second < r.second;
});
vector<vector<segm>> seg;
int l = Seg[1].first, r = Seg[1].second;
vector<segm> tmp;
tmp.emplace_back(l, r, 1);
for (int i = 2; i <= n; ++i) {
if (Seg[i].first > r) {
seg.emplace_back(tmp);
tmp.clear();
l = Seg[i].first, r = Seg[i].second;
tmp.emplace_back(l, r, i);
} else {
l = min(l, Seg[i].first);
r = max(r, Seg[i].second);
tmp.emplace_back(Seg[i].first, Seg[i].second, i);
}
}
seg.emplace_back(tmp);
int idx = 0, allok = 1;
for (vector<segm> v : seg) {
++idx;
int atm = 0;
for (int i = 0; i < v.size(); ++i)
atm += v[i].second - v[i].first;
sort(v.begin(), v.end(), [&](auto &l, auto &r) {
return l.id > r.id;
});
yhb[idx].tim = atm;
int l = 0, r = 1e16, best = -1;
while (l <= r) {
int mid = l + r >> 1;
int now = mid, ok = 1;
for (int i = 0; i < v.size(); ++i) {
now += v[i].second - v[i].first;
if (now > t[v[i].id]) {
ok = 0;
break;
}
}
if (ok) best = mid, l = mid + 1;
else r = mid - 1;
}
if (best == -1) {
allok = 0;
break;
}
yhb[idx].stt = best;
yhb[idx].todo = v;
}
if (!allok) cout << "No\n";
else {
sort(yhb + 1, yhb + idx + 1, [&](auto &l, auto &r) {
return l.stt < r.stt || l.stt == r.stt && l.tim < r.tim;
});
int ok = 1;
for (int i = 1; i <= idx; ++i) {
yhb[i].pref.resize(yhb[i].todo.size());
vector<segm> v;
for (int j = (int)yhb[i].todo.size() - 1; ~j; --j) {
v.emplace_back(yhb[i].todo[j]);
sort(v.begin(), v.end(), [&](auto &l, auto &r) {
return l.id > r.id;
});
int l = 0, r = 1e16, best = -1;
while (l <= r) {
int mid = l + r >> 1;
int now = mid, ok = 1;
for (int i = 0; i < v.size(); ++i) {
now += v[i].second - v[i].first;
if (now > t[v[i].id]) {
ok = 0;
break;
}
}
if (ok) best = mid, l = mid + 1;
else r = mid - 1;
}
if (best == -1) {
ok = 0;
goto please_ac;
}
yhb[i].pref[j] = best;
}
}
please_ac:;
if (!ok) {
cout << "No\n";
} else {
for (int i = 1; i <= n; ++i) len[i] = 0;
int now = 0;
for (int _ = 0; _ < n; ++_) {
int id = -1;
for (int i = 1; i <= idx; ++i)
if (len[i] < yhb[i].pref.size()) {
if (id == -1) id = i;
else if (yhb[id].pref[len[id]] > yhb[i].pref[len[i]]) id = i;
}
assert(~id);
now += yhb[id].todo[len[id]].second - yhb[id].todo[len[id]].first;
if (now > t[yhb[id].todo[len[id]].id]) {
ok = 0;
break;
}
++len[id];
}
cout << (ok ? "Yes" : "No") << '\n';
}
}
}
}
signed main() {
freopen("move.in", "r", stdin);
freopen("move.out", "w", stdout);
int c = read(), T = read();
while (T--) {
if (c <= 3) subtask1::solve();
else if (c == 4 || c == 8 || c == 12) subtask2::solve();
else if (c == 5 || c == 9 || c == 13 || c == 19 || c == 20) subtask3::solve();
else subtask4::solve();
}
return 0;
}
3a3b2c1c LV 1
京公网安备 11011102002149号