【BZOJ 4383】[POI2015] Pustynia

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4383
数据传送门:http://oi.cyo.ng/?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;
}

207 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.

  51. It’s actually very difficult in this active life to listen news
    on Television, thus I simply use web for that
    purpose, and obtain the hottest information.

  52. With havin so much content and articles do you ever run into any issues of plagorism or copyright infringement? My site has a lot of completely unique content I’ve either created myself or outsourced but it appears a lot of it is popping it up all over the web without my authorization. Do you know any techniques to help stop content from being stolen? I’d genuinely appreciate it.

  53. Thanks for the sensible critique. Me & my neighbor were just preparing to do some research about this. We got a grab a book from our local library but I think I learned more clear from this post. I’m very glad to see such fantastic info being shared freely out there.

  54. I simply couldn’t go away your site prior to suggesting that I actually enjoyed
    the standard info an individual provide to your guests? Is gonna be back steadily in order to investigate cross-check new posts

  55. Heya! I understand this is kind of off-topic but I had to ask.Does managing a well-established blog like yours take a large amount ofwork? I am brand new to blogging however I do write in mydiary everyday. I’d like to start a blog so I can share my personal experience and thoughts online.Please let me know if you have any recommendations or tips for brand new aspiring bloggers.Appreciate it!

  56. Thank you for the good writeup. It in fact was a amusement account it.
    Look advanced to more added agreeable from you! However, how can we communicate?

  57. Hiya, I am really glad I have found this info. Today bloggers publish only about gossip and internet stuff and this is actually frustrating. A good site with exciting content, that’s what I need. Thank you for making this website, and I will be visiting again. Do you do newsletters by email?

  58. Hi! I could have sworn I’ve been to this website before but after checking
    through some of the post I realized it’s new to me.
    Nonetheless, I’m definitely happy I found it and I’ll be bookmarking and
    checking back often!

  59. I’m excited to discover this page. I need to to thank you for your time just forthis wonderful read!! I definitely appreciated every little bit of it and I have you savedto fav to see new things in your site.

  60. hey there and thank you for your info – I’ve certainly picked up anything new from right here. I did however expertise some technical points using this web site, since I experienced to reload the website lots of times previous to I could get it to load correctly. I had been wondering if your hosting is OK? Not that I’m complaining, but sluggish loading instances times will often affect your placement in google and can damage your quality score if ads and marketing with Adwords. Anyway I’m adding this RSS to my email and could look out for a lot more of your respective interesting content. Ensure that you update this again soon..

  61. I have learned some points through your blog post post. One other stuff I would like to talk about is that there are numerous games on the market designed particularly for preschool age little ones. They involve pattern identification, colors, pets, and forms. These commonly focus on familiarization as an alternative to memorization. This will keep children and kids engaged without having a sensation like they are learning. Thanks

  62. Recorded Delivery peptan f 2000 hd A diplomatic war of words over the rocky Mediterranean outpost erupted in July after it built an artificial reef in contested waters using concrete blocks. Spain said the reef restricted access for its fishermen.

  63. Currently it appears like BlogEngine is the preferred blogging platform out there right now.
    (from what I’ve read) Is that what you are using on your blog?

  64. At this time it sounds like Movable Type is the top blogging platform available right now.

    (from what I’ve read) Is that what you’re using
    on your blog?

  65. Write more, thats all I have to say. Literally, it seems as though you relied on the
    video to make your point. You clearly know what youre talking about, why
    waste your intelligence on just posting videos to your blog when you
    could be giving us something informative to read?

  66. Excellent read, I just passed this onto a friend who was doing some research on that. And he just bought me lunch as I found it for him smile Therefore let me rephrase that: Thanks for lunch!

  67. Hiya, I’m really glad I have found this information. Today bloggers publish only about gossip and web stuff and this is really irritating. A good web site with interesting content, that’s what I need. Thanks for making this site, and I’ll be visiting again. Do you do newsletters by email?

  68. Wonderful goods from you, man. I’ve understand your stuff previous to and you’re just extremely excellent. I actually like what you have acquired here, really like what you’re saying and the way in which you say it. You make it enjoyable and you still care for to keep it smart. I can not wait to read much more from you. This is really a tremendous website.

  69. Wow that was unusual. I just wrote an incredibly long comment but after I clicked submit my comment didn’t appear. Grrrr… well I’m not writing all that over again. Anyways, just wanted to say superb blog!

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

  71. Just wish to say your article is as amazing. The clarity in your post is just nice and i can assume you’re an expert on this subject. Fine with your permission allow me to grab your RSS feed to keep up to date with forthcoming post. Thanks a million and please keep up the enjoyable work.

  72. I wonder why those servers with copyrighted content stay up. I see a lot of “don’t post any US content” but they don’t care at all about content from japan.. . Is it just that Japan doesn’t care much about their copyright laws?. . It is hundreds or maybe even thousands of servers with content from Japan but they only get DMCA warnings for US material or something that got translated by a US company.. . They also often have some content on their website, like images or small archives..

  73. This web site is really a walk-through for all of the info you wanted about this and didn at know who to ask. Glimpse here, and you all definitely discover it.

  74. I’ve been absent for some time, but now I remember why I used to love this web site. Thanks, I?¦ll try and check back more often. How frequently you update your site?

  75. Thanks for your personal marvelous posting! I seriously enjoyed reading it, you will be a great author.I will remember to bookmark your blog and definitely will come back someday.I want to encourage you to ultimately continue your great work, have a nice afternoon!

  76. I am typically to blogging i truly appreciate your site content. This article has truly peaks my interest. I am about to bookmark your internet site and maintain checking for brand spanking new information.

  77. Hey There. I discovered your blog using msn. That is an extremely well written article. I will make sure to bookmark it and return to learn extra of your useful info. Thank you for the post. I will certainly return.

  78. This is very interesting, You’re a very skilled blogger. I’ve joined your rss feed and look forward to seeking more of your excellent post. Also, I have shared your web site in my social networks!

  79. Hiya, I am really glad I have found this info. Today bloggers publish just about gossip and internet stuff and this is actually annoying. A good blog with interesting content, this is what I need. Thanks for making this web site, and I will be visiting again. Do you do newsletters by email?

  80. Hiya, I’m really glad I have found this info. Today bloggers publish only about gossip and web stuff and this is really irritating. A good web site with interesting content, that is what I need. Thanks for making this web site, and I will be visiting again. Do you do newsletters by email?

Leave a Reply to 메이저토토 Cancel reply

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