luogu 3488 [POI2009]LYZ-Ice Skates 线段树 + 思维
2024-08-28 05:17:21
Code:
#include <bits/stdc++.h>
#define setIO(s) freopen(s".in","r",stdin), freopen(s".out","w",stdout)
#define maxn 1000000
#define ll long long
#define lson (now<<1)
#define rson ((now<<1)|1)
using namespace std;
int n,m;
ll k,d;
ll sum[maxn<<2],lmx[maxn<<2],rmx[maxn<<2],mx[maxn<<2];
void pushup(int l,int r,int now) {
int mid=(l+r)>>1,ls=lson,rs=(r>mid)?rson:0;
sum[now]=sum[ls]+sum[rs];
lmx[now]=max(lmx[ls],sum[ls]+lmx[rs]);
rmx[now]=max(rmx[rs],sum[rs]+rmx[ls]);
mx[now]=rmx[ls]+lmx[rs];
mx[now]=max(mx[now], max(mx[ls], mx[rs]));
}
void build(int l,int r,int now) {
if(l==r) {
sum[now]=-k;
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson);
if(r>mid) build(mid+1,r,rson);
pushup(l,r,now);
}
void update(int l,int r,int now,int x,ll v) {
if(l==r) {
sum[now]+=v;
lmx[now]=rmx[now]=mx[now]=max(0ll, sum[now]);
return;
}
int mid=(l+r)>>1;
if(x<=mid) update(l,mid,lson,x,v);
else update(mid+1,r,rson,x,v);
pushup(l,r,now);
}
int main() {
// setIO("input");
scanf("%d%d%lld%lld",&n,&m,&k,&d);
build(1,n,1);
for(int i=1;i<=m;++i) {
int r;
ll x;
scanf("%d%lld",&r,&x);
update(1,n,1,r,x);
if(mx[1] > k*d) printf("NIE\n");
else printf("TAK\n");
}
return 0;
}
最新文章
- .cn根服务器被攻击之后
- thinkphp发送邮件
- 《javascript高级程序设计》第21章 Ajax和Comet
- 无可匹敌的创建job(细化很多细节)
- 试着开发chrome插件
- Android CTS 结果 testResult.xml 修改 fail 项 为 notExecuted 项 分析
- Cocos2d-x 2地图步行实现:SPFA算法
- 华为云(ECS)-linux服务器中-Ubuntu图形界面安装-解决root登录受限-VNCviwer/Teamviwer远程访问教程
- 简述ADO.NET(一)
- python绘制中文词云图
- idea去掉无效引用
- 深入浅出JavaScript(一)
- HTTP请求/响应报文结构
- Objective-C的泛型
- ACCESS_REFUSED - Login was refused using authentication mechanism PLAIN
- gulpjs的使用介绍及技巧
- windows 2008 r2 安装 owas 2013
- vue2.0实现一个模态弹框,内容自定义(使用slot)
- django学习笔记【004】创建带有model的app
- Leetcode 516.最长回文子序列