Stars in Your Window POJ - 2482
2024-08-29 12:58:48
错误记录:
题目说输入在int范围内,但是运算过程中可能超int;后来开了很多longlong就过了
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
struct Q
{
ll x1,x2,y;int c,type;
}q[];
int nq;
bool operator<(const Q &a,const Q &b)
{
return a.y<b.y||(a.y==b.y&&a.type<b.type);
}
int n,w,h;
ll ans;
namespace S
{
#define lc (num<<1)
#define rc (num<<1|1)
#define mid (l+((r-l)>>1))
ll d[],addv[];
void build(int l,int r,int num)
{
if(l==r) {d[num]=addv[num]=;return;}
build(l,mid,lc);build(mid+,r,rc);
d[num]=addv[num]=;
}
int L,R;ll x;
void pd(int l,int r,int num)
{
d[lc]+=addv[num];d[rc]+=addv[num];
addv[lc]+=addv[num];addv[rc]+=addv[num];
addv[num]=;
}
void _addx(int l,int r,int num)
{
if(L<=l&&r<=R)
{
d[num]+=x;addv[num]+=x;
return;
}
pd(l,r,num);
if(L<=mid) _addx(l,mid,lc);
if(mid<R) _addx(mid+,r,rc);
d[num]=max(d[lc],d[rc]);
}
ll _que(int l,int r,int num)
{
if(L<=l&&r<=R) return d[num];
pd(l,r,num);
ll ans=;
if(L<=mid) ans=max(ans,_que(l,mid,lc));
if(mid<R) ans=max(ans,_que(mid+,r,rc));
return ans;
}
#undef lc
#undef rc
#undef mid
}
map<ll,ll> ma;
ll t0[];
int main()
{
int i;ll a,b,c;
while(scanf("%d%d%d",&n,&w,&h)==)
{
nq=;
for(i=;i<=n;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
q[++nq].y=a-w+;q[nq].x1=b-h+;q[nq].x2=b;q[nq].c=c;q[nq].type=;
q[++nq].y=a+;q[nq].x1=b-h+;q[nq].x2=b;q[nq].c=c;q[nq].type=;
}
ans=;
t0[]=;
for(i=;i<=nq;i++) t0[++t0[]]=q[i].x1,t0[++t0[]]=q[i].x2;
sort(t0+,t0+t0[]+);t0[]=unique(t0+,t0+t0[]+)-t0-;
ma.clear();
for(i=;i<=t0[];i++) ma[t0[i]]=i;
for(i=;i<=nq;i++) q[i].x1=ma[q[i].x1],q[i].x2=ma[q[i].x2];
sort(q+,q+nq+);
S::build(,t0[],);
for(i=;i<=nq;i++)
{
if(q[i].type==)
{
S::L=q[i].x1;S::R=q[i].x2;S::x=-q[i].c;
S::_addx(,t0[],);
}
else
{
S::L=q[i].x1;S::R=q[i].x2;S::x=q[i].c;
S::_addx(,t0[],);
}
if(i==nq||q[i].y!=q[i+].y)
{
S::L=;S::R=t0[];
ans=max(ans,S::_que(,t0[],));
}
}
printf("%lld\n",ans);
}
return ;
}
最新文章
- BizTalk动手实验(十七)ODBC适配器使用
- OC-01 编译链接的作用
- WampServer服务中MySQL无法正常启动解决方案
- Stream,Reader/Writer,Buffered的区别(1)
- Autowired properities class
- Struts2中的类型转换
- An Attempt to Understand Boosting Algorithm(s)
- HDU3709:Balanced Number(数位DP+记忆化DFS)
- Java条形码/二维码生成和解析
- python函数前篇
- IDEA远程调试监控端口
- vue.js实战——计算属性
- 二分插入、bisect
- WinDbg基于管道的虚拟机Kernel Debugging
- spring_150908_hibernate_id_sequence
- Backbone.js 的最佳应用场景有哪些?#zhihu#
- oracle 存储过程 变量的声明和赋值的3种方式
- 绘制函数 y=x^2-2x-3/2x^2+2x+1 的曲线
- POJ3026 Borg Maze(Prim)(BFS)
- 动态配置log4j2.xml日志输出文件的位置
热门文章
- 基于ADB框架Robotium跨进程操作
- 解决移动端页面滚动后不触发touchend事件
- python day-01 (python基础知识1)
- Mongo.setReadPref(mode, tagSet) primaries and secondaries are treated equivalently. 读优先级策略
- pageHelper没有分页效果的问题
- MYSQL初级学习笔记三:数据的操作DML!(视频序号:初级_24,25,36)
- Github--开源代码仓库式系统(转)
- Cocos2d-X对常用Object-C特性的替换
- 监听屏幕旋转事件window. onorientationchange
- hadoop推荐