// n^2 - na male testy #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; void inline normalizuj(int& a, int& b) { int tmp = a; a = a < b ? a : b; b = tmp < b ? b : tmp; } struct Samochod { int startX1, startX2, startY1, startY2; int koniecX1, koniecX2, koniecY1, koniecY2; bool zaparkowany; int kolejnoscPoczatkowa, kolejnoscParkowania, wysokosc; void norm() { normalizuj(startX1, startX2); normalizuj(startY1, startY2); normalizuj(koniecX1, koniecX2); normalizuj(koniecY1, koniecY2); wysokosc = startY2 - startY1; } }; Samochod* samochodyPoczatkowa[50000]; Samochod* samochodyKoncowa[50000]; int maksWysokosc[50000]; bool sort1(const Samochod* s1, const Samochod* s2) { return s1->startX2 < s2->startX2; } bool sort2(const Samochod* s1, const Samochod* s2) { if (s1->koniecX1 == s2->koniecX1) { return s1->startX2 < s2->startX2; } return s1->koniecX1 < s2->koniecX1; } int main() { int licztaTestow; scanf("%d", &licztaTestow); for (int i = 0; i < 50000; ++i) { samochodyPoczatkowa[i] = new Samochod(); } for (int i = 0; i < licztaTestow; ++i) { int liczbaSamochodow, wysokoscParkingu; scanf("%d%d", &liczbaSamochodow, &wysokoscParkingu); for (int j = 0; j < liczbaSamochodow; ++j) { maksWysokosc[j] = 0; samochodyPoczatkowa[j]->zaparkowany = false; scanf("%d%d%d%d", &samochodyPoczatkowa[j]->startX1, &samochodyPoczatkowa[j]->startY1, &samochodyPoczatkowa[j]->startX2, &samochodyPoczatkowa[j]->startY2); } for (int j = 0; j < liczbaSamochodow; ++j) { scanf("%d%d%d%d", &samochodyPoczatkowa[j]->koniecX1, &samochodyPoczatkowa[j]->koniecY1, &samochodyPoczatkowa[j]->koniecX2, &samochodyPoczatkowa[j]->koniecY2); samochodyPoczatkowa[j]->norm(); samochodyKoncowa[j] = samochodyPoczatkowa[j]; } std::sort(samochodyKoncowa, samochodyKoncowa + liczbaSamochodow, sort2); for (int j = 0; j < liczbaSamochodow; ++j) { samochodyKoncowa[j]->kolejnoscParkowania = j; } std::sort(samochodyPoczatkowa, samochodyPoczatkowa + liczbaSamochodow, sort1); for (int j = 0; j < liczbaSamochodow; ++j) { samochodyPoczatkowa[j]->kolejnoscPoczatkowa = j; } bool parkowanieMozliwe = true; for (int j = 0; j < liczbaSamochodow; ++j) { Samochod* s = samochodyPoczatkowa[j]; int wysokosc = s->wysokosc; int x1 = liczbaSamochodow - (s->kolejnoscPoczatkowa + 1); int x2 = s->kolejnoscParkowania; if (x1 < x2) { for (int k = s->kolejnoscPoczatkowa + 1; k < liczbaSamochodow; ++k) { if (samochodyPoczatkowa[k]->kolejnoscParkowania < s->kolejnoscParkowania) { int maks = std::max(wysokosc, maksWysokosc[k]); if (maks > wysokoscParkingu - samochodyPoczatkowa[k]->wysokosc) { parkowanieMozliwe = false; break; } maksWysokosc[k] = maks; } } } else { for (int k = 0; k < s->kolejnoscParkowania; ++k) { if (samochodyKoncowa[k]->kolejnoscPoczatkowa > s->kolejnoscPoczatkowa) { int pocz = samochodyKoncowa[k]->kolejnoscPoczatkowa; int maks = std::max(wysokosc, maksWysokosc[pocz]); if (maks > wysokoscParkingu - samochodyPoczatkowa[pocz]->wysokosc) { parkowanieMozliwe = false; break; } maksWysokosc[pocz] = maks; } } } } if (parkowanieMozliwe) { printf("TAK\n"); } else { printf("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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | // n^2 - na male testy #include <cstdio> #include <cstdlib> #include <algorithm> using namespace std; void inline normalizuj(int& a, int& b) { int tmp = a; a = a < b ? a : b; b = tmp < b ? b : tmp; } struct Samochod { int startX1, startX2, startY1, startY2; int koniecX1, koniecX2, koniecY1, koniecY2; bool zaparkowany; int kolejnoscPoczatkowa, kolejnoscParkowania, wysokosc; void norm() { normalizuj(startX1, startX2); normalizuj(startY1, startY2); normalizuj(koniecX1, koniecX2); normalizuj(koniecY1, koniecY2); wysokosc = startY2 - startY1; } }; Samochod* samochodyPoczatkowa[50000]; Samochod* samochodyKoncowa[50000]; int maksWysokosc[50000]; bool sort1(const Samochod* s1, const Samochod* s2) { return s1->startX2 < s2->startX2; } bool sort2(const Samochod* s1, const Samochod* s2) { if (s1->koniecX1 == s2->koniecX1) { return s1->startX2 < s2->startX2; } return s1->koniecX1 < s2->koniecX1; } int main() { int licztaTestow; scanf("%d", &licztaTestow); for (int i = 0; i < 50000; ++i) { samochodyPoczatkowa[i] = new Samochod(); } for (int i = 0; i < licztaTestow; ++i) { int liczbaSamochodow, wysokoscParkingu; scanf("%d%d", &liczbaSamochodow, &wysokoscParkingu); for (int j = 0; j < liczbaSamochodow; ++j) { maksWysokosc[j] = 0; samochodyPoczatkowa[j]->zaparkowany = false; scanf("%d%d%d%d", &samochodyPoczatkowa[j]->startX1, &samochodyPoczatkowa[j]->startY1, &samochodyPoczatkowa[j]->startX2, &samochodyPoczatkowa[j]->startY2); } for (int j = 0; j < liczbaSamochodow; ++j) { scanf("%d%d%d%d", &samochodyPoczatkowa[j]->koniecX1, &samochodyPoczatkowa[j]->koniecY1, &samochodyPoczatkowa[j]->koniecX2, &samochodyPoczatkowa[j]->koniecY2); samochodyPoczatkowa[j]->norm(); samochodyKoncowa[j] = samochodyPoczatkowa[j]; } std::sort(samochodyKoncowa, samochodyKoncowa + liczbaSamochodow, sort2); for (int j = 0; j < liczbaSamochodow; ++j) { samochodyKoncowa[j]->kolejnoscParkowania = j; } std::sort(samochodyPoczatkowa, samochodyPoczatkowa + liczbaSamochodow, sort1); for (int j = 0; j < liczbaSamochodow; ++j) { samochodyPoczatkowa[j]->kolejnoscPoczatkowa = j; } bool parkowanieMozliwe = true; for (int j = 0; j < liczbaSamochodow; ++j) { Samochod* s = samochodyPoczatkowa[j]; int wysokosc = s->wysokosc; int x1 = liczbaSamochodow - (s->kolejnoscPoczatkowa + 1); int x2 = s->kolejnoscParkowania; if (x1 < x2) { for (int k = s->kolejnoscPoczatkowa + 1; k < liczbaSamochodow; ++k) { if (samochodyPoczatkowa[k]->kolejnoscParkowania < s->kolejnoscParkowania) { int maks = std::max(wysokosc, maksWysokosc[k]); if (maks > wysokoscParkingu - samochodyPoczatkowa[k]->wysokosc) { parkowanieMozliwe = false; break; } maksWysokosc[k] = maks; } } } else { for (int k = 0; k < s->kolejnoscParkowania; ++k) { if (samochodyKoncowa[k]->kolejnoscPoczatkowa > s->kolejnoscPoczatkowa) { int pocz = samochodyKoncowa[k]->kolejnoscPoczatkowa; int maks = std::max(wysokosc, maksWysokosc[pocz]); if (maks > wysokoscParkingu - samochodyPoczatkowa[pocz]->wysokosc) { parkowanieMozliwe = false; break; } maksWysokosc[pocz] = maks; } } } } if (parkowanieMozliwe) { printf("TAK\n"); } else { printf("NIE\n"); } } return 0; } |