欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}
相关标签: 数据结构