#include
<
cstdio
>
#include
<
cstring
>
#include
<
cstdlib
>
using
namespace
std;
struct
node{
int
x,y,z;
}m[
3100
];
int
N,M;
int
ans;
int
c[
5100
];
int
a[
5100
];
inline
int
lowbit(
int
x)
{
return
x
^
(x
&
(x
-
1
)); }
int
cmp(
const
void
*
A,
const
void
*
B)
{
node
*
aa
=
(node
*
)A,
*
bb
=
(node
*
)B;
if
(aa
->
y
!=
bb
->
y)
return
aa
->
y
-
bb
->
y;
else
return
aa
->
x
-
bb
->
x;
}
int
getsum(
int
x)
{
int
sum
=
0
;
while
(x){
sum
+=
c[x];
x
-=
lowbit(x);
}
return
sum;
}
void
modify(
int
x)
{
while
(x
<=
N){
c[x]
++
;
x
+=
lowbit(x);
}
}
int
main()
{
scanf(
"
%d%d
"
,
&
N,
&
M);
for
(
int
i
=
1
;i
<=
M;
++
i)
scanf(
"
%d%d%d
"
,
&
m[i].x,
&
m[i].y,
&
m[i].z);
qsort(m
+
1
,M,
sizeof
(node),cmp);
memset(a,
0
,
sizeof
(a));
ans
=
0
;
for
(
int
i
=
1
;i
<=
M;
++
i){
int
val
=
m[i].z
-
(getsum(m[i].y)
-
getsum(m[i].x
-
1
));
for
(
int
j
=
m[i].y;j
>=
m[i].x;
--
j){
if
(val
<=
0
)
break
;
if
(a[j]
==
0
){
a[j]
=
1
;
modify(j);
val
--
;
ans
++
;
}
}
}
printf(
"
%d\n
"
,ans);
return
0
;
}
posted on 2009-08-11 10:25
xfstart07 阅读(201)
评论(0) 编辑 收藏 引用