【Codeforces 781E】Andryusha and Nervous Barriers

相关链接

题目传送门:http://codeforces.com/contest/781/problem/E
代码参考:http://codeforces.com/contest/781/submission/25269119

解题报告

这题我们先考虑没有墙会害怕的版本
这样的话,我们想象一下是墙冲向一排点
于是搞一个线段树支持区间赋值,区间查询就可以了!

现在考虑加上害怕的限制
那我们可以用二维线段树!
但好难写QwQ ←这货写到一半就弃坑了

于是就去看别人的代码
然后看到了毛爷爷的代码 (毛爷爷这场暴跌 默哀 _(:з」∠)_
然后发现这题又可以暴力………

我们考虑将每一次分开的点打成一包
算上最开始的,不难发现总共只有$O(w+2n)$个包
那每一个包我们插到线段树中,此时总包数是$O((w+2n) \log (w+2n))$的
那么每一次查询我们就暴力每一个节点,于是均摊的复杂度仍然是$O(\log n)$的
代码好写还跑得飞快!

这种有一点暴力思想的数据结构题,我还真的是一点想不出来啊!
比如BZOJ 4712,真的是一点都没往那边想啊!
我一定要在科技树上点亮这个技能!

Code

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

const int N = 5000000;
const int M = 200009;
const int MOD = 1000000007;

int hit,wid,n,cnt;
struct Pack{int h,sum,del;}p[N];
struct Wall{int h,l,r,s;}wall[M];

class Segment_Tree{
	int ans_tmp,tot,root,ch[M][2];
	stack<int> s[M];
	public:
		inline void insert(int p, int id) {
			insert(root, 1, wid, p, id);
		}
		inline int query(int h, int l, int r) {
			ans_tmp = 0; 
			query(root, 1, wid, l, r, h);
			return ans_tmp;
		}
	private:
		void insert(int &w, int l, int r, int p, int v) {
			if (!w) w = ++tot; s[w].push(v);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) insert(ch[w][0], l, mid-1, p, v);
				else insert(ch[w][1], mid, r, p, v);
			}
		}
		void query(int w, int l, int r, int L, int R, int h) {
			if (L <= l && r <= R) {
				while (!s[w].empty() && p[s[w].top()].h <= h) {
					if (!p[s[w].top()].del) {
						p[s[w].top()].del = 1;
						(ans_tmp += p[s[w].top()].sum) %= MOD;	
					} s[w].pop();
				}
			} else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, h);
				if (mid <= R) query(ch[w][1], mid, r, L, R, h);
			}
		}
}SGT;

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;
}

int main() {
	hit = read(); wid = read(); n = read();
	for (int i=1;i<=n;i++) {
		wall[i].h = read();
		wall[i].l = read();
		wall[i].r = read();
		wall[i].s = read();
	}
	for (int i=1;i<=wid;i++) {
		p[++cnt].h = hit + 1;
		p[cnt].sum = 1;
		SGT.insert(i, cnt); 
	} 
	sort(wall+1, wall+1+n, [](const Wall &A, const Wall &B){return A.h > B.h;});
	for (int i=1,h_mx,tmp;i<=n;i++) { 
		tmp = SGT.query(wall[i].h + wall[i].s, wall[i].l, wall[i].r);
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		p[++cnt].sum = tmp; p[cnt].h = wall[i].h;
		if (wall[i].l == 1) SGT.insert(wall[i].r+1, cnt-1);
		else SGT.insert(wall[i].l-1, cnt-1);
		if (wall[i].r == wid) SGT.insert(wall[i].l-1, cnt);
		else SGT.insert(wall[i].r+1, cnt);
	}
	int vout = 0;
	for (int i=1;i<=cnt;i++) 
		(vout += (p[i].del ^ 1) * p[i].sum) %= MOD;
	printf("%d\n",vout);
	return 0;
}

336 thoughts to “【Codeforces 781E】Andryusha and Nervous Barriers”

  1. 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 success. If you know of any please share.
    Kudos!

  2. Hi! I could have sworn I’ve visited this website before but after looking at a few of the articles I realized it’s new to me.
    Nonetheless, I’m definitely delighted I came across it and I’ll be book-marking it and checking back
    often!

  3. I like the helpful information you provide in your articles.
    I will bookmark your weblog and check again here regularly.
    I am quite sure I’ll learn lots of new stuff right here! Best of luck for the next!

  4. certainly like your web site however you have to test the spelling on quite a few of your
    posts. A number of them are rife with spelling problems and I find it very
    troublesome to inform the reality however I will
    definitely come back again.

  5. Great blog here! Also your site loads up fast!

    What host are you using? Can I get your affiliate link to your host?
    I wish my website loaded up as fast as yours lol

  6. I know this if off topic but I’m looking into starting my own blog and was wondering what all
    is required to get set up? I’m assuming having a blog like yours would
    cost a pretty penny? I’m not very internet smart so I’m not 100% positive.
    Any tips or advice would be greatly appreciated. Thank you

  7. Hello there! 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 success.
    If you know of any please share. Thank you!

  8. Please let me know if you’re looking for a article writer for your weblog.
    You have some really good posts and I feel I would be a good asset.
    If you ever want to take some of the load off, I’d love
    to write some articles for your blog in exchange for a link back to mine.

    Please shoot me an e-mail if interested. Thanks!

  9. Hello! This is my 1st comment here so I just wanted
    to give a quick shout out and tell you I really enjoy reading through your articles.

    Can you suggest any other blogs/websites/forums that cover the same topics?
    Thanks a lot!

  10. I’m really loving the theme/design of your weblog. Do you ever run into any browser compatibility problems?
    A couple of my blog audience have complained about my website not operating correctly in Explorer but looks great in Firefox.
    Do you have any ideas to help fix this problem?

  11. My developer 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 import all my
    wordpress content into it? Any kind of help would be greatly appreciated!

  12. Thanks for another informative site. The
    place else may I am getting that type of information written in such a perfect means?
    I’ve a venture that I am just now operating on, and I have
    been at the look out for such information.

  13. hello there and thank you for your information – I have certainly picked
    up anything new from right here. I did however expertise several technical points
    using this website, since I experienced to reload the website a lot of times previous to I could get it to
    load correctly. I had been wondering if your web hosting is OK?
    Not that I am complaining, but sluggish loading instances times
    will sometimes affect your placement in google and could damage your high-quality score if advertising and marketing with Adwords.
    Anyway I’m adding this RSS to my e-mail and can look out for a lot more of your respective interesting content.
    Make sure you update this again soon.

  14. I blog quite often and I truly appreciate your content.
    This great article has really peaked my interest. I’m going to
    bookmark your website and keep checking for new information about once per week.
    I opted in for your Feed as well. natalielise plenty of fish

  15. Hi there! I know this is kinda off topic nevertheless I’d figured I’d ask.

    Would you be interested in trading links or maybe guest authoring a blog post or vice-versa?
    My site addresses a lot of the same subjects as yours and I think we could greatly
    benefit from each other. If you might be interested feel free
    to send me an email. I look forward to hearing from you!
    Wonderful blog by the way!

  16. I’m really enjoying the design and layout of your site.
    It’s a very easy on the eyes which makes it much more pleasant for
    me to come here and visit more often. Did you hire out a developer to create your theme?
    Fantastic work!

  17. I do agree with all the ideas you have introduced in your post.

    They are very convincing and can certainly work.

    Nonetheless, the posts are too brief for newbies. May just you please lengthen them a bit from next time?

    Thank you for the post.

  18. Fantastic items from you, man. I have be aware your stuff previous
    to and you are just too fantastic. I actually like what you’ve obtained here, certainly like what you’re saying
    and the way through which you are saying it. You’re making it enjoyable and you continue
    to take care of to stay it smart. I cant wait to learn much more from you.
    This is really a great site.

  19. First off I would like to say awesome 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 mind prior to writing. I’ve had a difficult time clearing my thoughts in getting my thoughts out there.

    I truly do take pleasure in writing however it just seems
    like the first 10 to 15 minutes are wasted
    simply just trying to figure out how to begin.
    Any ideas or tips? Cheers!

  20. You could certainly see your skills within the work you write.
    The sector hopes for even more passionate writers such as you who are not afraid to
    mention how they believe. All the time go after your heart.

  21. I truly love your blog.. Pleasant colors & theme.
    Did you build this web site yourself? Please reply back as I’m hoping to
    create my own site and want to learn where you got
    this from or exactly what the theme is named.

    Many thanks!

  22. I just like the helpful information you provide to your
    articles. I’ll bookmark your weblog and check again here regularly.
    I am quite certain I’ll learn a lot of new stuff right here!

    Good luck for the next!

  23. An outstanding share! I have just forwarded this onto a co-worker who had been conducting a little research on this.

    And he in fact bought me breakfast simply because I
    discovered it for him… lol. So let me reword this….
    Thank YOU for the meal!! But yeah, thanx for spending some time to discuss this issue here on your web
    site.

  24. Magnificent beat ! I would like to apprentice while you
    amend your web site, how could i subscribe for a blog
    website? The account helped me a acceptable deal.
    I had been tiny bit acquainted of this your broadcast offered
    bright clear concept

  25. I’m not sure where you’re getting your info, but great topic.

    I needs to spend some time learning much more or understanding more.

    Thanks for excellent information I was looking for this information for my mission.

  26. Very great post. I simply stumbled upon your weblog and
    wished to say that I have truly enjoyed surfing around your weblog posts.
    In any case I will be subscribing for your feed and
    I hope you write again soon!

  27. My coder is trying to persuade 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 anxious about switching to another platform.
    I have heard good things about blogengine.net.
    Is there a way I can import all my wordpress content into it?

    Any kind of help would be greatly appreciated!

  28. I’m curious to find out what blog platform you have
    been utilizing? I’m experiencing some minor security issues with my
    latest website and I’d like to find something more secure.
    Do you have any recommendations?

  29. Hey I know this is off topic but I was wondering if
    you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates.

    I’ve been looking for a plug-in like this for quite
    some time and was hoping maybe you would have some experience with something
    like this. Please let me know if you run into anything.
    I truly enjoy reading your blog and I look forward to your new
    updates.

  30. Im no longer sure where you are getting your info, but good topic. I must spend a while studying more or understanding more. Thanks for fantastic info I used to be searching for this info for my mission.

  31. Hi there! This is my first comment here so I just wanted to
    give a quick shout out and tell you I genuinely enjoy reading through your articles.
    Can you recommend any other blogs/websites/forums that deal with the
    same subjects? Thanks a lot!

  32. Hey there! Do you use Twitter? I’d like to follow you if that
    would be ok. I’m undoubtedly enjoying your blog and look forward to new updates.

  33. Wow that was strange. I just wrote an really
    long comment but after I clicked submit my comment didn’t show
    up. Grrrr… well I’m not writing all that over again. Regardless, just wanted to say superb blog!

  34. I simply couldn’t leave your web site before suggesting that I really loved the usual information a
    person provide for your visitors? Is going to be again steadily to inspect new posts

  35. Hey there! This is my first comment here so I just wanted to give a quick shout out and tell you I truly enjoy reading your blog posts.
    Can you recommend any other blogs/websites/forums that go over
    the same subjects? Thanks for your time!

  36. Once I originally commented I clicked the -Notify me when new comments are added- checkbox and now every time a comment is added I get 4 emails with the identical comment. Is there any means you possibly can remove me from that service? Thanks!

  37. You’ve made some good points there. I looked on the web for more information about the issueand found most people will go along with your views on this web site.Nyeste Fodboldtrøjer

  38. Hi! Quick question that’s completely off topic. Do you know how to make your site mobile friendly? My blog looks weird when browsing from my iphone 4. I’m trying to find a template or plugin that might be able to correct this issue. If you have any recommendations, please share. Cheers!

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

  40. My wife and i were so happy John could complete his research via the ideas he was given out of your blog. It’s not at all simplistic to simply be making a gift of helpful hints that some people may have been trying to sell. We really consider we now have you to be grateful to for this. All the illustrations you have made, the simple web site navigation, the friendships you will help foster – it is everything unbelievable, and it’s really making our son and our family reason why this subject matter is satisfying, which is certainly really pressing. Thank you for all the pieces!

  41. Heya i’m for the first time here. I found this board and I to find It reallyhelpful & it helped me out a lot. I hope to provide something backand aid others like you aided me.

  42. hermes beltsI抎 should check with you here. Which is not one thing I often do! I get pleasure from reading a publish that can make people think. Also, thanks for allowing me to comment!

  43. It’s actually a great and useful piece of information. I’mglad that you shared this useful information withus. Please stay us informed like this. Thank you for sharing.

  44. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this. Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your new updates.|

  45. Very nice post. I just stumbled upon your weblog and wanted to mention that I’ve really loved surfing around your weblog posts. In any case I’ll be subscribing on your feed and I am hoping you write once more soon!|

  46. Thank you a lot for sharing this with all folks you really recognize what you are talking approximately! Bookmarked. Kindly also seek advice from my site =). We may have a link alternate agreement between us|

  47. Heya i’m for the first time here. I came across this board and I find It really useful & it helped me out much. I hope to give something back and help others like you helped me.

  48. Hello there! I know this is kinda off topic but I was wondering if you knew where I could find a captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having problems finding one? Thanks a lot!|

  49. An interesting discussion is worth comment. I think that you should write more on this subject matter, it might not be a taboo subject but generally folks don’t talk about these subjects. To the next! Many thanks!!|

  50. You made some decent points there. I checked on the web for more info about the issue and found most people will go along with your views on this website.|

发表评论

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