显然只用判断两个会相交的车会不会卡住就行了。
直接树状数组维护后缀最大值就行了。
代码：
#include<bits/stdc++.h>using namespace std;const int N=5e4+5;struct Matrix{int x1,x2,w,id;}a1[N],a2[N];int n,T,W,pos[N],bit[N];inline int lowbit(int x){return x&-x;}inline void update(int x,int v){for(int i=x;i;i-=lowbit(i))bit[i]=max(bit[i],v);}inline int query(int x){int ret=0;for(int i=x;i<=n;i+=lowbit(i))ret=max(ret,bit[i]);return ret;}inline bool cmp(const Matrix&a,const Matrix&b){return a.x1==b.x1?a.x2<b.x2:a.x1<b.x1;}const int RLEN=1<<18;inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)); return (ib==ob) ? -1 : *ib++;}inline int read() { char ch=nc(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+(ch^48); ch=nc();} return i*f;}int main(){ T=read(); while(T--){ n=read(),W=read(); for(int i=1,y1,y2;i<=n;++i){ a1[i].x1=read(),y1=read(),a1[i].x2=read(),y2=read(),a1[i].id=i; if(a1[i].x1>a1[i].x2)swap(a1[i].x1,a1[i].x2); a1[i].w=abs(y1-y2); } for(int i=1,y1,y2;i<=n;++i){ a2[i].x1=read(),y1=read(),a2[i].x2=read(),y2=read(),a2[i].id=i; if(a2[i].x1>a2[i].x2)swap(a2[i].x1,a2[i].x2); a2[i].w=abs(y1-y2); } bool f=1; sort(a1+1,a1+n+1,cmp),sort(a2+1,a2+n+1,cmp); for(int i=1;i<=n;++i)pos[a1[i].id]=i; for(int i=1;i<=n;++i){ if(query(pos[a2[i].id])+a2[i].w>W){f=false;break;} update(pos[a2[i].id],a2[i].w); } fill(bit+1,bit+n+1,0),puts(f?"TAK":"NIE"); } return 0;}
