#include <cstdio> #include <algorithm> #include <map> struct car_t { int x1, x2, w, i; }; bool compByX1(const car_t& a, const car_t& b) { return a.x1 < b.x1; } bool compByX2(const car_t& a, const car_t& b) { return a.x2 < b.x2; } inline int abs(const int a) { return a >= 0 ? a : -a; } inline int min(const int a, const int b) { return a < b ? a : b; } car_t cars[50000]; void test() { int n, w; scanf("%d %d", &n, &w ); for( int i = 0; i < n; i++ ) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d ); cars[i].x1 = min(a,c); cars[i].w = abs(b-d); } for( int i = 0; i < n; i++ ) { int a, c; scanf("%d %*s %d %*s", &a, &c ); cars[i].x2 = min(a,c); } std::sort(cars, cars+n, compByX1); for( int i = 0; i < n; i++ ) cars[i].i = i; std::sort(cars, cars+n, compByX2); std::map<int, int> Cross; Cross[n] = 0; for( int i = 0; i < n; i++ ) { //fprintf(stderr, "NEW CAR: wysokosc=%d\n", cars[i].w ); //for( = Cross.begin(); it != Cross.end(); it++ ) // fprintf(stderr, "(%d,%d) ", it->first, it->second ); //fprintf(stderr,"\n"); int cross = Cross.lower_bound(cars[i].i)->second; if( cars[i].w+cross > w ) { puts("NIE"); //fprintf(stderr, "%d collided with %d\n", cars[i].i, Cross.lower_bound(cars[i].i)->first); return; } if( cars[i].w > cross ) { Cross[cars[i].i] = cars[i].w; std::map<int, int>::iterator it = Cross.find(cars[i].i); --it; while( it != Cross.end() and it->second < cars[i].w ) { std::map<int, int>::iterator rit = it; --it; Cross.erase(rit); } } } puts("TAK"); } int main() { int T; scanf("%d", &T ); while( T --> 0 ) test(); }
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 | #include <cstdio> #include <algorithm> #include <map> struct car_t { int x1, x2, w, i; }; bool compByX1(const car_t& a, const car_t& b) { return a.x1 < b.x1; } bool compByX2(const car_t& a, const car_t& b) { return a.x2 < b.x2; } inline int abs(const int a) { return a >= 0 ? a : -a; } inline int min(const int a, const int b) { return a < b ? a : b; } car_t cars[50000]; void test() { int n, w; scanf("%d %d", &n, &w ); for( int i = 0; i < n; i++ ) { int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d ); cars[i].x1 = min(a,c); cars[i].w = abs(b-d); } for( int i = 0; i < n; i++ ) { int a, c; scanf("%d %*s %d %*s", &a, &c ); cars[i].x2 = min(a,c); } std::sort(cars, cars+n, compByX1); for( int i = 0; i < n; i++ ) cars[i].i = i; std::sort(cars, cars+n, compByX2); std::map<int, int> Cross; Cross[n] = 0; for( int i = 0; i < n; i++ ) { //fprintf(stderr, "NEW CAR: wysokosc=%d\n", cars[i].w ); //for( = Cross.begin(); it != Cross.end(); it++ ) // fprintf(stderr, "(%d,%d) ", it->first, it->second ); //fprintf(stderr,"\n"); int cross = Cross.lower_bound(cars[i].i)->second; if( cars[i].w+cross > w ) { puts("NIE"); //fprintf(stderr, "%d collided with %d\n", cars[i].i, Cross.lower_bound(cars[i].i)->first); return; } if( cars[i].w > cross ) { Cross[cars[i].i] = cars[i].w; std::map<int, int>::iterator it = Cross.find(cars[i].i); --it; while( it != Cross.end() and it->second < cars[i].w ) { std::map<int, int>::iterator rit = it; --it; Cross.erase(rit); } } } puts("TAK"); } int main() { int T; scanf("%d", &T ); while( T --> 0 ) test(); } |