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
#include <iostream>     
#include <algorithm>    
#include <vector>       

using namespace std;

struct Car{
    int height;
    int leftEdge;
    Car* predecessor;
    Car* successor;
    Car(){
        this->predecessor = NULL;
        this->successor = NULL;
    }
};

struct ComparableCarPointer{
    struct Car* carPointer;
    ComparableCarPointer(Car* _carPointer=NULL){
        this->carPointer = _carPointer;
    }
    bool operator< (const ComparableCarPointer& right){
        return this->carPointer->leftEdge < right.carPointer->leftEdge;
    };
};

int main () {
    short int remaingTests;
    int amountOfCars, parkingHeight;
    Car* cars;
    vector<ComparableCarPointer> carOrderPtrs;
    bool possibleToRearrange;
    int x1,y1,x2,y2;
    
    cin >> remaingTests;
    
    while(remaingTests>0){
        remaingTests--;
        cin >> amountOfCars >> parkingHeight;
        cars = new Car[amountOfCars];
        
        for(int id = 0; id < amountOfCars; id++){
            cin >> x1 >> y1 >> x2 >> y2;
            cars[id].height = abs(y2-y1);
            cars[id].leftEdge = min(x1,x2);
            carOrderPtrs.push_back(ComparableCarPointer(&cars[id]));
        }
        
        make_heap (carOrderPtrs.begin(),carOrderPtrs.end());
        sort_heap (carOrderPtrs.begin(),carOrderPtrs.end());
        
        if(amountOfCars>1){ //for head and tail of queue
            carOrderPtrs[0].carPointer->successor = carOrderPtrs[1].carPointer;
            carOrderPtrs[amountOfCars-1].carPointer->predecessor = carOrderPtrs[amountOfCars-2].carPointer;
        }
        for(int orderID = 1; orderID < amountOfCars-1; orderID++){ //for middle elements of queue
            carOrderPtrs[orderID].carPointer->predecessor = carOrderPtrs[orderID-1].carPointer;
            carOrderPtrs[orderID].carPointer->successor = carOrderPtrs[orderID+1].carPointer;
        }
        
        for(int id = 0; id < amountOfCars; id++){
            cin >> x1 >> y1 >> x2 >> y2;
            cars[id].leftEdge = min(x1,x2);
        }
        
        make_heap (carOrderPtrs.begin(),carOrderPtrs.end());
        sort_heap (carOrderPtrs.begin(),carOrderPtrs.end());
        
        possibleToRearrange = true;
        for(int orderID = 0; (orderID < amountOfCars) && (possibleToRearrange); orderID++){ //for middle elements of queue
            Car* currentlyMovedCarPtr = carOrderPtrs[orderID].carPointer;
            Car* nextCarToPassPtr = currentlyMovedCarPtr->predecessor;
            if(currentlyMovedCarPtr->successor != NULL){
                currentlyMovedCarPtr->successor->predecessor = nextCarToPassPtr; 
            }
            if(nextCarToPassPtr != NULL){
                nextCarToPassPtr->successor = currentlyMovedCarPtr->successor;
                
                int currentlyMovedCarHeight = currentlyMovedCarPtr->height;
                do{
                    if(currentlyMovedCarHeight + nextCarToPassPtr->height <= parkingHeight){
                        nextCarToPassPtr = nextCarToPassPtr->predecessor;
                    }
                    else{
                        possibleToRearrange = false;
                        nextCarToPassPtr = NULL;
                    }
                }while(nextCarToPassPtr != NULL);
                
            }
        }
        
        cout << (possibleToRearrange ? "TAK\n" : "NIE\n");
        
        carOrderPtrs.clear();
        delete [] cars;
    }
    return 0;
};