[PA2014]Parking

题目大意：

停车场是一个宽度为\(w(w\le10^9)\)的矩形。我们以其左下角顶点为原点，坐标轴平行于矩形的边，建立直角坐标系。停车场很长，我们可以认为它一直向右边伸展到无穷远处。

总共有\(n(n\le5\times10^4)\)辆车。车都是边平行于坐标轴的矩形，大小可能不同。你可以将车在停车场内任意地平移，且不能互相重叠。

告诉你每辆车目前的位置和目标位置，求是否可以通过移动达到目标状态。

思路：

如果两辆车路线必定会相交，且两辆车宽度加起来大于\(w\)，那么就不能达到目标状态。

从右到左枚举目标状态中的车，树状数组按照初始状态维护从左到右的前缀最大值即可。

源代码：

#include<cstdio>

#include<cctype>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

const int N=5e4+1;

int n,w,rank[N];

struct Rect {

	int x1,x2,w,id;

	void read() {

		int y1,y2;

		x1=getint();

		y1=getint();

		x2=getint();

		y2=getint();

		w=std::abs(y1-y2);

		if(x1>x2) std::swap(x1,x2);

	}

	bool operator < (const Rect &rhs) const {

		if(x1==rhs.x1) return x2<rhs.x2;

		return x1<rhs.x1;

	}

};

Rect s[N],t[N];

class FenwickTree {

	private:

		int val[N];

		int lowbit(const int &x) const {

			return x&-x;

		}

	public:

		void reset() {

			std::fill(&val[1],&val[n]+1,0);

		}

		void modify(int p,const int &x) {

			for(;p<=n;p+=lowbit(p)) {

				val[p]=std::max(val[p],x);

			}

		}

		int query(int p) const {

			int ret=0;

			for(;p;p-=lowbit(p)) {

				ret=std::max(ret,val[p]);

			}

			return ret;

		}

};

FenwickTree bit;

int main() {

	for(register int T=getint();T;T--) {

		n=getint(),w=getint();

		bit.reset();

		for(register int i=1;i<=n;i++) {

			s[i].read();

			s[i].id=i;

		}

		for(register int i=1;i<=n;i++) {

			t[i].read();

			t[i].id=i;

		}

		std::sort(&s[1],&s[n]+1);

		std::sort(&t[1],&t[n]+1);

		for(register int i=1;i<=n;i++) {

			rank[s[i].id]=i;

		}

		for(register int i=n;i>=1;i--) {

			if(bit.query(rank[t[i].id])+t[i].w>w) {

				puts("NIE");

				goto Next;

			}

			bit.modify(rank[t[i].id],t[i].w);

		}

		puts("TAK");

		Next:;

	}

	return 0;

}

巴特西

[PA2014]Parking

[PA2014]Parking

题目大意：

思路：

源代码：

最新文章

热门文章