BZOJ 1135 POI 2009 Lyz線分ツリー+Hall定理
1~n型のスケート靴があって、それぞれk足があって、1つのx番の足の人は[x,x+d]号のスケート靴に適応することしかできなくて、毎回いくつかx番の足の人を増加してあるいはいくつかx番の足の人を減らして、一致することができるかどうかを聞きます
http://m.blog.csdn.net/blog/u012732945/40707885
OTZ
この問題は私がWAに貢献できるなんて酔っ払った.
http://m.blog.csdn.net/blog/u012732945/40707885
OTZ
この問題は私がWAに貢献できるなんて酔っ払った.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 200200
using namespace std;
struct abcd{
long long l_max,r_max,_max,sum;
abcd() {}
abcd(long long _)
{
l_max=max(_,0ll);
r_max=max(_,0ll);
_max=max(_,0ll);
sum=_;
}
friend abcd operator + (const abcd &x,const abcd &y)
{
abcd re;
re.l_max=max(x.l_max,x.sum+y.l_max);
re.r_max=max(y.r_max,y.sum+x.r_max);
re._max=max(max(x._max,y._max),x.r_max+y.l_max);
re.sum=x.sum+y.sum;
return re;
}
};
long long n,m,k,d;
struct Segtree{
Segtree *ls,*rs;
abcd status;
void* operator new (size_t)
{
static Segtree mempool[M<<1],*C=mempool;
return C++;
}
void Build_Tree(int x,int y)
{
int mid=x+y>>1;
if(x==y)
{
new (&status)abcd(-k);
return ;
}
(ls=new Segtree)->Build_Tree(x,mid);
(rs=new Segtree)->Build_Tree(mid+1,y);
status=ls->status+rs->status;
}
void Modify(int x,int y,int pos,int val)
{
int mid=x+y>>1;
if(x==y)
{
new (&status)abcd(status.sum+val);
return ;
}
if(pos<=mid)
ls->Modify(x,mid,pos,val);
else
rs->Modify(mid+1,y,pos,val);
status=ls->status+rs->status;
}
}*tree=new Segtree;
int main()
{
int i,x,y;
cin>>n>>m>>k>>d;
tree->Build_Tree(1,n);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
tree->Modify(1,n,x,y);
puts(tree->status._max<=k*d?"TAK":"NIE");
}
return 0;
}