#include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <utility> using namespace std; int t, n, w; int cars[50001][3]; // x_begin, x_end, height vector<pair<int, int> > begins(50001, make_pair(0,0)); //x_begin, index vector<pair<int, int> > ends(50001, make_pair(0,0)); //x_end, index int mapping[50001]; // mapping car_index -> beginning position int tree[100010]; // heights (with beginning position) bool cmp_begins(pair<int, int> a, pair<int, int> b) { return a.first < b.first; } void insert(int x, int val) { int v = n + x - 1; tree[v] = val; while ( v != 1) { v /= 2; tree[v] = max(tree[2*v], tree[2*v+1]); } } int query(int a) { // 0 - (a-1) int va = n, vb = n + (a - 1); if (va == vb) return 0; int wyn = tree[va]; if (va != vb) wyn = max(wyn, tree[vb]); while (va / 2 != vb / 2) { if (va % 2 == 0) wyn = max(wyn, tree[va + 1]); /* prawa bombka na lewej ścieżce */ if (vb % 2 == 1) wyn = max(wyn, tree[vb - 1]); /* lewa bombka na prawej ścieżce */ va /= 2; vb /= 2; } return wyn; } int main() { scanf("%d", &t); while(t--) { scanf("%d%d", &n, &w); bool correct = true; int a, b, c, d; for(int i=0; i< 100005; ++i) tree[i] = 0; // w sumie to powinno już być wyczyszczone for(int i=1; i<=n; i++) { scanf("%d%d%d%d", &a, &b, &c, &d); cars[i][2] = abs(b - d); cars[i][0] = min(a, c); begins[i].first = cars[i][0]; begins[i].second = i; } for(int i=1; i<=n; i++) { scanf("%d%d%d%d", &a, &b, &c, &d); cars[i][1] = min(a, c); ends[i].first = cars[i][1]; ends[i].second = i; } sort(begins.begin() + 1, begins.begin() + n + 1, cmp_begins); sort(ends.begin(), ends.begin() + n + 1, cmp_begins); // consider using new comparator for(int i=1; i<=n; i++) { mapping[begins[i].second] = i; insert(i, cars[begins[i].second][2]); // printf("begins[%d].first = %d second = %d\n", i, begins[i].first, begins[i].second); // printf("ends[%d].first = %d second = %d\n", i, ends[i].first, ends[i].second); // printf("height %d -> %d\n", i, heights[i]); } // for(int i=0; i<=2*n; ++i) // printf("tree[%d] = %d\n", i, tree[i]); for (int i=1; i<=n && correct; i++) { a = ends[i].second; b = mapping[a]; insert(b, 0); c = query(b); d = cars[ends[i].second][2]; // printf("Node %d (real %d, height %d) has at the left height %d\n", b, a, d, c); if (c + d> w) correct = false; // printf("tree:\n"); // for(int i=0; i<=2*n; ++i) // printf("tree[%d] = %d\n", i, tree[i]); } printf(correct ? "TAK\n" : "NIE\n"); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | #include <cstdio> #include <cstdlib> #include <algorithm> #include <vector> #include <utility> using namespace std; int t, n, w; int cars[50001][3]; // x_begin, x_end, height vector<pair<int, int> > begins(50001, make_pair(0,0)); //x_begin, index vector<pair<int, int> > ends(50001, make_pair(0,0)); //x_end, index int mapping[50001]; // mapping car_index -> beginning position int tree[100010]; // heights (with beginning position) bool cmp_begins(pair<int, int> a, pair<int, int> b) { return a.first < b.first; } void insert(int x, int val) { int v = n + x - 1; tree[v] = val; while ( v != 1) { v /= 2; tree[v] = max(tree[2*v], tree[2*v+1]); } } int query(int a) { // 0 - (a-1) int va = n, vb = n + (a - 1); if (va == vb) return 0; int wyn = tree[va]; if (va != vb) wyn = max(wyn, tree[vb]); while (va / 2 != vb / 2) { if (va % 2 == 0) wyn = max(wyn, tree[va + 1]); /* prawa bombka na lewej ścieżce */ if (vb % 2 == 1) wyn = max(wyn, tree[vb - 1]); /* lewa bombka na prawej ścieżce */ va /= 2; vb /= 2; } return wyn; } int main() { scanf("%d", &t); while(t--) { scanf("%d%d", &n, &w); bool correct = true; int a, b, c, d; for(int i=0; i< 100005; ++i) tree[i] = 0; // w sumie to powinno już być wyczyszczone for(int i=1; i<=n; i++) { scanf("%d%d%d%d", &a, &b, &c, &d); cars[i][2] = abs(b - d); cars[i][0] = min(a, c); begins[i].first = cars[i][0]; begins[i].second = i; } for(int i=1; i<=n; i++) { scanf("%d%d%d%d", &a, &b, &c, &d); cars[i][1] = min(a, c); ends[i].first = cars[i][1]; ends[i].second = i; } sort(begins.begin() + 1, begins.begin() + n + 1, cmp_begins); sort(ends.begin(), ends.begin() + n + 1, cmp_begins); // consider using new comparator for(int i=1; i<=n; i++) { mapping[begins[i].second] = i; insert(i, cars[begins[i].second][2]); // printf("begins[%d].first = %d second = %d\n", i, begins[i].first, begins[i].second); // printf("ends[%d].first = %d second = %d\n", i, ends[i].first, ends[i].second); // printf("height %d -> %d\n", i, heights[i]); } // for(int i=0; i<=2*n; ++i) // printf("tree[%d] = %d\n", i, tree[i]); for (int i=1; i<=n && correct; i++) { a = ends[i].second; b = mapping[a]; insert(b, 0); c = query(b); d = cars[ends[i].second][2]; // printf("Node %d (real %d, height %d) has at the left height %d\n", b, a, d, c); if (c + d> w) correct = false; // printf("tree:\n"); // for(int i=0; i<=2*n; ++i) // printf("tree[%d] = %d\n", i, tree[i]); } printf(correct ? "TAK\n" : "NIE\n"); } return 0; } |