【BZOJ 2794】[POI2012] Cloakroom




然而有了这两个东西,而且复杂度要求O(1)询问,这样我就不会了 QwQ



★,°:.☆( ̄▽ ̄)/$:.°★ 。


#define LL long long
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const int INF = 100000;

struct Event{
	int a,b,c,d;
	inline Event() {}
	inline Event(int _a, int _b, int _c):a(_a),b(_b),c(_c) {}
	inline bool operator < (const Event &B) const {return a < B.a;}

int f[M],arr[M+N<<1],vout[M],tot,n,m,mx;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;

int main() {
	n = read();
	for (int i=1,a,b,c;i<=n;i++) {
		a = read(); b = read(); c = read();
		arr[++tot] = c; arr[++tot] = b;
		t[i] = Event(b, c, a);
	m = read();
	for (int i=1,a,b,c;i<=m;i++) {
		a = read(); b = read(); c = read() + a;
		arr[++tot] = a; arr[++tot] = c;
		q[i] = Event(a, c, b);
		q[i].d = i;
	sort(arr+1, arr+1+tot);
	tot = unique(arr+1, arr+1+tot) - arr - 1;
	for (int i=1;i<=n;i++) {
		t[i].a = lower_bound(arr+1, arr+1+tot, t[i].a) - arr;
		t[i].b = lower_bound(arr+1, arr+1+tot, t[i].b) - arr;
		mx = max(mx, t[i].a);
	for (int i=1;i<=m;i++) {
		q[i].a = lower_bound(arr+1, arr+1+tot, q[i].a) - arr;
		q[i].b = lower_bound(arr+1, arr+1+tot, q[i].b) - arr;
		q[i].a = min(q[i].a, mx);
	sort(t+1, t+1+n);
	sort(q+1, q+1+m);
	f[0] = 1e9;
	for (int j=1,p1=1;j<=m;j++) {
		for (;t[p1].a<=q[j].a&&p1<=n;p1++) {
			for (int i=INF-t[p1].c,to=INF;i>=0;i--,to--) {
				f[to] = max(f[to], min(f[i], t[p1].b));	
		vout[q[j].d] = f[q[j].c] > q[j].b;
	for (int i=1;i<=m;i++) {
		if (vout[i]) puts("TAK");
		else puts("NIE");
	return 0;

23 thoughts to “【BZOJ 2794】[POI2012] Cloakroom”

  1. Hi! Do you know if they make any plugins to assist with SEO?
    I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good results.
    If you know of any please share. Appreciate it!

  2. Simply want to say your article is as astounding.
    The clearness in your publish is just excellent and i could assume you
    are knowledgeable in this subject. Fine with your permission allow me to snatch your RSS feed to stay
    updated with approaching post. Thank you one million and please continue the enjoyable work.

  3. We stumbled over here by a different web page and thought I might as well check things out.
    I like what I see so now i’m following you. Look forward to looking over your web page repeatedly.

  4. Oh my goodness! Awesome article dude! Thank you, However
    I am experiencing issues with your RSS. I don’t understand the
    reason why I cannot join it. Is there anyone else having identical RSS problems?

    Anyone that knows the answer can you kindly respond? Thanx!!

  5. Excellent blog here! Also your website loads up
    very fast! What host are you using? Can I get your affiliate link to your host?

    I wish my web site loaded up as quickly as yours lol

  6. Hi! Someone in my Myspace group shared this website with us so
    I came to give it a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers!
    Great blog and amazing style and design.

  7. Do you mind if I quote a few of your articles as long as I provide credit
    and sources back to your blog? My blog site is in the very same area
    of interest as yours and my visitors would genuinely
    benefit from some of the information you present here.
    Please let me know if this okay with you. Thanks a lot!

  8. Hello I am so delighted I found your blog, I really found you by error, while I
    was researching on Askjeeve for something else, Regardless I am here now and would just like to say
    cheers for a tremendous post and a all round enjoyable blog (I also love the
    theme/design), I don’t have time to browse it all at
    the minute but I have bookmarked it and also
    added your RSS feeds, so when I have time I will be back to read a
    great deal more, Please do keep up the great work.

  9. Today, I went to the beachfront with my children. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is totally off topic but I had to tell someone!

  10. Hi there, You have done a great job. I’ll definitely digg it and personally suggest
    to my friends. I am sure they will be benefited from this website.

  11. It’s the best time to make some plans for the future and it is time to be happy.

    I have read this post and if I could I desire to suggest you few interesting things or
    advice. Perhaps you could write next articles referring to this article.
    I want to read even more things about it!

  12. Wow, marvelous blog layout! How long have you been blogging for?

    you make blogging look easy. The overall look of your
    site is fantastic, as well as the content!

  13. Hello! Quick question that’s entirely off topic.
    Do you know how to make your site mobile friendly?
    My site looks weird when viewing from my iphone 4.

    I’m trying to find a theme or plugin that might be able to resolve
    this problem. If you have any suggestions, please share.

  14. Hi! Someone in my Myspace group shared this website with us so I
    came to check it out. I’m definitely enjoying the information. I’m
    bookmarking and will be tweeting this to my followers! Fantastic blog and great design and style.

Leave a Reply

Your email address will not be published. Required fields are marked *