注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Codeforces Round #179 (Div. 2)  

2013-04-12 13:42:47|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
This contest is a little hard for me. Only A and C were solved finally though I spent more than one hour on the other problems. My rank is 213. Here is the summary:

Pro A:
There are n elements in an array.If we can obtain an array where any two neighboring elements would be distinct in a finite time,print "YES" and print "NO" otherwise.
This problem is not hard.What we should do is just counting the amount of each elements and find the max amount k.If k-1 is bigger than n-k,then print "NO" and print "YES" otherwise.

Pro C:
The first line tells us three integers n, m, k(1<=n,m,k<=10^5).
The second line is an array(f) of n elements.
Next m lines contain operations with three integers li, ri, di(1<=li<=ri<=n,0<=di<=10^5) which means to increase all array elements with numbers li,li+1,...,ri by value di.
Next k lines contain queries with two integers x, y(1<=xi<=yi<=m) which means that one should apply operations with numbers xi,xi+1,...,?yi to the array.
After understanding this problem,I thought of the segment tree firstly with the max data 10^5.But after I analysed carefully,I find another convenient solution.
First of all, we need to know how many times each operations need to apply by k queries.We need an array(p) with each element is 0 initially.Then come k queries and execute two commands:p[xi]++ and p[yi+1]--.After cycling from 1 to m with executing command:p[i]+=p[i-1],we can know the i-th  operation needs to apply p[i] times.
Secondly,we multiply each operation's di by p[i].
Thirdly,we need to know how much each element needs to add by m operations.The following is similar to the first.As mentioned,we need an array(p) with each element is 0 initially.Then come m operations and execute two commands:p[li]+=di and p[ri+1]-=di.After cycling from 1 to n with executing command:p[i]+=p[i-1],we can know each element f[i] needs to add p[i].
Finally,after cycling from 1 to n with executing command:f[i]+=p[i],we can obtain the answers.
*Tips:as the data will be very big,we should use __int64 replace of int.
  评论这张
 
阅读(96)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018