#include
<
iostream
>
using
namespace
std;
struct
Node{
int
a,b,Max,cover;
int
lc,rc;
}Tree[
150000
];
int
C,S,R;
int
Tot;
inline
int
max(
int
a,
int
b){
return
a
>
b
?
a:b;
}
void
build(
int
l,
int
r){
Tot
++
;
int
Now
=
Tot;
Tree[Now].a
=
l;
Tree[Now].b
=
r;
Tree[Now].Max
=
0
;
Tree[Now].cover
=
0
;
if
(r
-
l
>
1
){
int
mid
=
(l
+
r)
>>
1
;
Tree[Now].lc
=
Tot
+
1
;
build(l,mid);
Tree[Now].rc
=
Tot
+
1
;
build(mid,r);
}
}
void
insert(
int
Num,
int
l,
int
r,
int
v){
if
(l
<=
Tree[Num].a
&&
r
>=
Tree[Num].b){
Tree[Num].cover
+=
v;
Tree[Num].Max
+=
v;
return
;
}
int
mid
=
(Tree[Num].a
+
Tree[Num].b)
>>
1
;
if
(r
<=
mid) insert(Tree[Num].lc,l,r,v);
else
if
(l
>=
mid) insert(Tree[Num].rc,l,r,v);
else
{
insert(Tree[Num].lc,l,r,v);
insert(Tree[Num].rc,l,r,v);
}
Tree[Num].Max
=
max(Tree[Tree[Num].lc].Max,Tree[Tree[Num].rc].Max)
+
Tree[Num].cover;
}
bool
query(
int
Num,
int
l,
int
r,
int
v,
int
s){
if
(Tree[Num].b
-
Tree[Num].a
==
1
){
if
(s
-
Tree[Num].Max
>=
v)
return
1
;
else
return
0
;
}
if
(s
-
Tree[Num].Max
>=
v)
return
1
;
int
mid
=
(Tree[Num].a
+
Tree[Num].b)
>>
1
;
if
(r
<=
mid)
return
query(Tree[Num].lc,l,r,v,s
-
Tree[Num].cover);
else
if
(l
>=
mid)
return
query(Tree[Num].rc,l,r,v,s
-
Tree[Num].cover);
else
{
return
query(Tree[Num].lc,l,mid,v,s
-
Tree[Num].cover)
&&
query(Tree[Num].rc,mid,r,v,s
-
Tree[Num].cover);
}
}
int
main()
{
freopen(
"
railway.in
"
,
"
r
"
,stdin);
freopen(
"
railway.out
"
,
"
w
"
,stdout);
scanf(
"
%d%d%d
"
,
&
C,
&
S,
&
R);
Tot
=
0
;
build(
0
,C
-
1
);
for
(
int
i
=
1
;i
<=
R;
++
i){
int
a,b,c;
scanf(
"
%d%d%d
"
,
&
a,
&
b,
&
c);
if
(query(
1
,a
-
1
,b
-
1
,c,S)){
printf(
"
YES\n
"
);
insert(
1
,a
-
1
,b
-
1
,c);
}
else
printf(
"
NO\n
"
);
}
return
0
;
}
posted on 2009-04-25 21:09
xfstart07 阅读(134)
评论(0) 编辑 收藏 引用 所属分类:
代码库