2018.10.29 bzoj3718: [PA2014]Parking(树状数组)
程序员文章站
2022-05-22 09:57:14
...
传送门
显然只用判断两个会相交的车会不会卡住就行了。
直接树状数组维护后缀最大值就行了。
代码:
#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;
}