【BZOJ 4383】[POI2015] Pustynia

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4383
数据传送门:https://oi.qizy.tech/?attachment_id=1911

题解

这个题暴力差分肯定可以做,就是边太多会爆炸
于是我们考虑先建一个像线段树一样的图
于是原题可以拆成6e5个区间连边
每一个区间又可以拆成log(n)个线段树上的点
于是复杂度就对辣!

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000000;
const int M = 5000000;
const int INF = 1000000000;

int head[N],to[M],nxt[M],cost[M],val[N],arr[N];
int sol[N],vis[N],in[N],n,m,s,bas,tot;
queue<pair<int,int> > leaf;

inline void Add_Edge(int u, int v, int w) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; 
	head[u] = T; cost[T] = w;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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;
}

void build(int w, int l, int r) {
	bas = max(bas, w);
	if (l < r) {
		int mid = l + r + 1 >> 1;
		Add_Edge(w, w<<1, 0); build(w<<1, l, mid - 1);
		Add_Edge(w, w*2+1, 0); build(w*2+1, mid, r);
	} else {
		leaf.push(make_pair(w,l));
	}
}

bool Get_Ans(int w) {
	sol[w] = true;
	for (int i=head[w];i;i=nxt[i]) {
		if (vis[to[i]] && val[w] - cost[i] < val[to[i]]) {
			return false;
		} else {
			val[to[i]] = min(val[to[i]], val[w] - cost[i]);
			if (--in[to[i]] == 0) {
				if (!Get_Ans(to[i])) {
					return false;
				};
			}
		}
	}
	return true;
}

inline bool solve() {
	for (int i=1;i<=tot;i++) {
		if (!sol[i] && !in[i]) {
			if (!Get_Ans(i)) {
				return false;
			}
		}
	}
	return true;
} 

void insert(int w, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		Add_Edge(tot, w, 0);
	} else {
		int mid = l + r + 1 >> 1;
		if (L < mid) insert(w<<1, l, mid-1, L, R);
		if (R >= mid) insert(w*2+1, mid, r, L, R);
	}
}

int main(){
	n = read(); s = read(); m = read();
	build(1,1,n);
	while (!leaf.empty()) { 
		Add_Edge(leaf.front().first, leaf.front().second + bas, 0);
		leaf.pop(); 
	}
	tot = bas + n;
	fill(val, val+N, INF);
	for (int i=1,p;i<=s;i++) {
		p = read();
		val[p+bas] = read();
		vis[p+bas] = 1;
	}
		
	for (int i=1,l,r,k,last;i<=m;i++) {
		l = read(); r = read(); 
		k = read(); ++tot;
		for (int j=1,tmp;j<=k;j++) {
			arr[j] = tmp = read();
			Add_Edge(bas+tmp, tot, 1);
		}
		arr[0] = l-1; arr[k+1] = r+1;
		for (int j=1;j<=k+1;j++) {
			if (arr[j] - arr[j-1] > 1) {
				insert(1,1,n,arr[j-1]+1,arr[j]-1);
			} 
		}
	}
	if (!solve()) {
		puts("NIE");
	} else {
		for (int i=bas;i<=tot;i++) {
			if (in[i] || val[i] < 1) {
				puts("NIE");
				exit(0);
			}
		}
		
		puts("TAK");
		for (int i=1;i<=n;i++) 
			printf("%d ",val[i+bas]);
	}
	return 0;
}

147 thoughts to “【BZOJ 4383】[POI2015] Pustynia”

  1. Definitely imagine that which you said. Your favorite justification seemed to be at the net the easiest thing to be aware of.
    I say to you, I certainly get irked even as other folks think about issues
    that they plainly don’t know about. You managed to hit the nail upon the top and defined out
    the whole thing with no need side-effects , folks can take a signal.
    Will likely be back to get more. Thanks

  2. You could definitely see your skills within the work you write.

    The arena hopes for more passionate writers such as you who are not afraid
    to say how they believe. Always follow your heart.

  3. Definitely consider that that you said. Your favourite reason appeared to be at the web the simplest
    thing to be aware of. I say to you, I certainly get irked
    at the same time as other folks consider worries that they just do not understand
    about. You managed to hit the nail upon the top and
    defined out the whole thing without having side effect , people could take a
    signal. Will likely be back to get more. Thank you

  4. Hi, i read your blog from time to time and i own a similar one and
    i was just wondering if you get a lot of spam responses?
    If so how do you prevent it, any plugin or anything you can recommend?

    I get so much lately it’s driving me insane so any support is very much appreciated.

  5. My partner and I absolutely love your blog and find the majority of your post’s to be exactly
    what I’m looking for. Do you offer guest writers to write content available for
    you? I wouldn’t mind composing a post or elaborating on a lot
    of the subjects you write related to here. Again, awesome web log!

  6. I think what you posted made a lot of sense.
    But, what about this? what if you added a little
    content? I am not suggesting your information isn’t good, however what
    if you added a title that makes people want more? I mean 【BZOJ 4383】[POI2015] Pustynia – Qizy's Database is kinda plain. You ought to peek at Yahoo’s home page and watch how they write post headlines to
    get viewers to click. You might try adding a video or a related
    picture or two to grab readers interested about what you’ve got to say.

    Just my opinion, it could make your blog a little livelier.

  7. I do not even know the way I ended up here,
    however I thought this put up used to be good.
    I do not recognise who you’re however definitely you’re going to
    a well-known blogger for those who aren’t already.

    Cheers!

  8. Thanks for your personal marvelous posting! I certainly enjoyed reading it, you’re a great author.
    I will make sure to bookmark your blog and will often come back in the foreseeable future.

    I want to encourage you to ultimately continue your great
    writing, have a nice evening!

  9. I like what you guys are up too. This type of clever work
    and exposure! Keep up the great works guys I’ve incorporated you guys to my own blogroll.
    natalielise pof

  10. Hey! I know this is somewhat off-topic but I needed to ask.
    Does operating a well-established website like yours require a massive
    amount work? I am brand new to writing a blog but
    I do write in my diary daily. I’d like to start a blog so I can easily
    share my personal experience and views online.
    Please let me know if you have any recommendations or tips for brand new
    aspiring bloggers. Appreciate it! plenty of fish natalielise

  11. I do trust all of the concepts you’ve offered to
    your post. They are very convincing and will
    definitely work. Still, the posts are very short for newbies.
    May you please lengthen them a little from subsequent time?
    Thanks for the post.

  12. You really make it seem really easy with your presentation however I in finding this
    topic to be actually something which I believe I would never understand.
    It sort of feels too complex and extremely extensive for me.
    I am looking ahead on your next publish, I’ll try to get the grasp of it!
    natalielise pof

  13. Wonderful website you have here but I was curious about if
    you knew of any message boards that cover the same topics talked about in this article?
    I’d really love to be a part of community where I can get feed-back from other knowledgeable people that share the same interest.
    If you have any recommendations, please let me know.
    Thank you!

  14. Hey there! Someone in my Myspace group shared this site with us so I
    came to look it over. I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my
    followers! Great blog and outstanding design and style.

  15. Howdy! Do you know if they make any plugins to help 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.
    Thanks!

  16. magnificent submit, very informative. I wonder why
    the opposite specialists of this sector do not understand
    this. You must proceed your writing. I am sure, you’ve a great readers’ base already!

  17. My coder is trying to convince me to move to .net from PHP.

    I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using Movable-type on various
    websites for about a year and am nervous about switching to another platform.
    I have heard excellent things about blogengine.net. Is there a way I can transfer all my wordpress posts into it?
    Any help would be really appreciated!

  18. Hello there! I know this is kinda off topic nevertheless I’d figured I’d ask.
    Would you be interested in exchanging links or maybe guest authoring a blog post or vice-versa?
    My blog covers a lot of the same topics as yours
    and I believe we could greatly benefit from each other.
    If you happen to be interested feel free to send me an email.
    I look forward to hearing from you! Fantastic blog by the way!

  19. First off I would like to say wonderful blog! I had a quick question that
    I’d like to ask if you do not mind. I was curious
    to know how you center yourself and clear your head prior
    to writing. I’ve had difficulty clearing my thoughts in getting my ideas out.
    I do take pleasure in writing but it just
    seems like the first 10 to 15 minutes are wasted simply
    just trying to figure out how to begin. Any suggestions or tips?
    Cheers!

  20. I believe this is one of the such a lot vital information for
    me. And i am happy reading your article. But wanna observation on some
    general issues, The site taste is great, the articles is in point of fact excellent
    : D. Just right job, cheers

  21. Hello, I think your website might be having browser compatibility issues.

    When I look at your blog site in Firefox, it looks fine but when opening in Internet Explorer, it has some overlapping.

    I just wanted to give you a quick heads up! Other then that, awesome blog!

  22. “Hello, i think that i saw you visited my web site thus i came to return the favor.I am attempting to find things to enhance my site!I suppose its ok to use a few of your ideas!!”

  23. Hmm is anyone else encountering problems with the pictures on this
    blog loading? I’m trying to determine if its
    a problem on my end or if it’s the blog. Any suggestions
    would be greatly appreciated.

  24. Terrific article! This is the kind of info that are
    meant to be shared around the net. Shame on Google for not positioning this put up upper!
    Come on over and consult with my website . Thank you =)

  25. Thanks a bunch for sharing this with all people you
    actually recognize what you’re talking about! Bookmarked.
    Kindly also seek advice from my web site =). We may have a link exchange arrangement among us

  26. It’s a pity you don’t have a donate button! I’d most
    certainly donate to this brilliant blog! I guess
    for now i’ll settle for book-marking and adding
    your RSS feed to my Google account. I look forward to brand new
    updates and will talk about this website with
    my Facebook group. Chat soon!

  27. Thanks for the marvelous posting! I seriously enjoyed reading it,
    you will be a great author.I will be sure to bookmark your blog and definitely will come back later
    on. I want to encourage continue your great work, have a nice weekend!

  28. Hiya, I am really glad I’ve found this info. Today bloggers publish just about gossip and web stuff and this is actually irritating. A good blog with exciting content, this is what I need. Thank you for making this website, and I will be visiting again. Do you do newsletters by email?

  29. Hello there! This article could not be written any better!Reading through this post reminds me of my previous roommate!He always kept preaching about this. I am going to send this information tohim. Pretty sure he’ll have a great read. Thankyou for sharing!

  30. Excellent blog! Do you have any suggestions for aspiring writers?
    I’m planning to start my own blog soon but I’m a little
    lost on everything. Would you propose starting with a free platform like WordPress or go
    for a paid option? There are so many options out there that
    I’m completely confused .. Any recommendations? Thanks a lot!

  31. Thanks for the auspicious writeup. It in reality was once a entertainment account it. Look complicated to more added agreeable from you! However, how can we keep in touch?

  32. Hello there. I found your blog by way of Google at the same time as looking for a related subject, your website got here up. It appears to be great. I have bookmarked it in my google bookmarks to visit then.

  33. Pretty nice post. I just stumbled upon your weblog and wished to say that I have truly enjoyed browsing your blog posts. After all I’ll be subscribing to your rss feed and I hope you write again soon!

  34. Hey there! I’m at work browsing your blog from my new iphone!

    Just wanted to say I love reading through your blog and look forward
    to all your posts! Keep up the great work!

  35. Palletized UK Goods Storage for International Shoppers, International shipping, Shipping items, Shipping items on a pallet, too heavy, too large, normal parcel, shipping palletized goods, international destination, packing a pallet, Palletized UK goods, Storage for international shoppers, Shipping service from the UK, Shipping service

  36. Awesome post. I am a regular visitor of your web site and appreciate you taking the time to maintain the nice site. I’ll be a frequent visitor for a really long time.

  37. Wow! This could be one particular of the most beneficial blogs We have ever arrive across on this subject. Basically Magnificent. I am also an expert in this topic so I can understand your effort.

  38. Thanks a lot for sharing this with all folks you actually recognise what you are talking approximately!
    Bookmarked. Please additionally visit my web site =).

    We can have a link trade arrangement between us

  39. Hey there! I’ve been reading your web site for some time now and finally got the courage to go
    ahead and give you a shout out from Lubbock Texas! Just wanted to mention keep up the excellent job!

  40. HelloGreetingsHey thereHeyGood dayHowdyHi thereHello thereHi! I know this is kindasomewhatkind of off topic but I was wondering which blog platform are you using for this sitewebsite? I’m getting tiredfed upsick and tired of WordPress because I’ve had issuesproblems with hackers and I’m looking at optionsalternatives for another platform. I would be greatawesomefantastic if you could point me in the direction of a good platform.

  41. The other day, while I was at work, my sister stole my apple ipad and
    tested to see if it can survive a thirty foot drop, just so she can be a youtube sensation. My apple ipad is now broken and she has 83 views.

    I know this is totally off topic but I had to share it
    with someone!

  42. Every weekend i used to visitgo to seepay a visitpay a quick visit this websiteweb sitesiteweb page, becauseasfor the reason that i wantwish for enjoyment, sinceasfor the reason that this this websiteweb sitesiteweb page conations reallyactuallyin facttrulygenuinely nicepleasantgoodfastidious funny stuffinformationdatamaterial too.

  43. I do trust all the ideas you’ve offered to your post.

    They’re very convincing and can certainly work.
    Nonetheless, the posts are very short for novices.
    May just you please lengthen them a little from subsequent time?
    Thank you for the post.

  44. I would like to express thanks to you just for rescuing me from such a circumstance. Because of exploring through the online world and meeting recommendations which were not helpful, I figured my life was done. Being alive devoid of the strategies to the issues you have solved all through the write-up is a serious case, and ones which might have adversely affected my career if I hadn’t discovered your web blog. Your primary ability and kindness in handling every aspect was very useful. I am not sure what I would’ve done if I had not come upon such a step like this. I am able to at this time look forward to my future. Thank you so much for this skilled and amazing help. I won’t hesitate to recommend your web sites to any person who desires support about this subject matter.

  45. Hi! This is my 1st comment here so I just wanted to give a quick
    shout out and say I truly enjoy reading through your
    posts. Can you recommend any other blogs/websites/forums that deal with the same topics?
    Many thanks!

  46. I am now not sure the place you’re getting your information, but good topic.
    I must spend a while studying much more or working out more.
    Thanks for fantastic info I was on the lookout for this info for my mission.

  47. I am now not certain the place you’re getting your information,
    however great topic. I must spend a while studying much more
    or understanding more. Thanks for great information I was looking for this info for my mission.

  48. Good post. I learn something new and challenging on sites I stumbleupon everyday.
    It will always be useful to read content from other writers and use a little something from
    their web sites.

  49. Great goods from you, man. I have understand your stuff previous to and you’re just extremely wonderful.

    I really like what you have acquired here, really like what you are stating and the way in which
    you say it. You make it entertaining and you still take care of
    to keep it wise. I can’t wait to read much more from you. This
    is really a wonderful site.

  50. You have made some good points there. I checked on the web
    to find out more about the issue and found most individuals
    will go along with your views on this website.

发表评论

电子邮件地址不会被公开。 必填项已用*标注