题目链接

非常不容易的一道题,把每个点向右上构造一个矩形,将问题转化为重合矩形那个亮度最大,注意LL,注意排序。

 #include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
#define maxn 50100
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL __int64
struct node
{
LL lx,rx,y;
LL s;
node(){}
node(LL a,LL b,LL c,LL d):lx(a),rx(b),y(c),s(d){}
bool operator < (const node &S) const
{
if(y == S.y)
return s > S.s;
else
return y < S.y;
}
}mat[maxn];
LL que[*maxn];
LL tree[*maxn];
LL lz[*maxn];
void pushup(int rt)
{
tree[rt] = max(tree[rt<<],tree[rt<<|]);
}
void pushdown(int rt)
{
if(lz[rt])
{
lz[rt<<] += lz[rt];
lz[rt<<|] += lz[rt];
tree[rt<<] += lz[rt];
tree[rt<<|] += lz[rt];
lz[rt] = ;
}
}
void update(int L,int R,int c,int l,int r,int rt)
{
int m;
if(L <= l&&r <= R)
{
tree[rt] += c;
lz[rt] += c;
return ;
}
pushdown(rt);
m = (l+r)>>;
if(L <= m)
update(L,R,c,lson);
if(R > m)
update(L,R,c,rson);
pushup(rt);
}
int bin(LL x,int n)
{
int str,mid,end;
str = ;
end = n;
while(str <= end)
{
mid = (str+end)/;
if(que[mid] == x)
return mid;
else if(que[mid] > x)
end = mid - ;
else
str = mid + ;
}
return mid;
}
int main()
{
int n,num,k,i;
LL a,b,c,h,w;
while(scanf("%d%I64d%I64d",&n,&w,&h)!=EOF)
{
num = ;
w--;
h--;
for(i = ;i < n;i ++)
{
scanf("%I64d%I64d%I64d",&a,&b,&c);
mat[num] = node(a,a+w,b,c);
que[num++] = a;
mat[num] = node(a,a+w,b+h,-c);
que[num++] = a+w;
}
k = ;
sort(que,que+num);
sort(mat,mat+num);
for(i = ;i < num;i ++)
{
if(que[i] != que[i-])
que[k++] = que[i];
}
LL maxz = ;
memset(tree,,sizeof(tree));
memset(lz,,sizeof(lz));
for(i = ;i < num;i ++)
{
int l = bin(mat[i].lx,k-);
int r = bin(mat[i].rx,k-);
if(l <= r) update(l,r,mat[i].s,,k-,);
maxz = max(maxz,tree[]);
}
printf("%I64d\n",maxz);
}
return ;
}

最新文章

  1. Alpha版本十天冲刺——Day 5
  2. 原生js tab 栏切换
  3. Mac 安装mysql5.7 注意事项
  4. Ubuntu14.04安装JDK与配置环境变量
  5. js执行顺序&lt;转&gt;
  6. HDU 4348 To the moon 可持久化线段树
  7. 将caffe训练时loss的变化曲线用matlab绘制出来
  8. Linux C 文件与目录2 文件的打开与关闭
  9. lintcode:线段树的修改
  10. Selenium2Library系列 keywords 之 _SelectElementKeywords 之 get_selected_list_values(self, locator)
  11. C#内存修改
  12. UESTC_王之盛宴 2015 UESTC Training for Graph Theory&lt;Problem K&gt;
  13. 一个AVRUSB作品HID类
  14. CS0433: 类型“BasePage”同一时候存在于“c:\Windows\Microsoft.NETxxxxxxxxxxxxxxxx
  15. python中文字符串编码问题
  16. cpio用法详细说明
  17. java工具类(五)之日期格式字符串与日期实现互转
  18. 【49】java内部类剖析
  19. Prometheus监控elasticsearch集群(以elasticsearch-6.4.2版本为例)
  20. html、css基础整理

热门文章

  1. [BZOJ3545] [ONTAK2010]Peaks(线段树合并 + 离散化)
  2. linux虚拟机无法上网 Network is unreachable
  3. SpringBoot项目整合Druid进行统计监控
  4. gridview和detailsview的完美结合运用实现增删改
  5. HDU 4474 Yet Another Multiple Problem【2012成都regional K题】 【BFS+一个判断技巧】
  6. golang并发编程goroutine+channel(一)
  7. 每日记录 2016-4-29 HTML5本地存储
  8. CODEVS_2144 砝码称重 2 折半搜索+二分查找+哈希
  9. Effective Java P2 Item1 Consider static factory methods instead of constructors
  10. jquery 实现鼠标点击div盒子移动功能