Pagini recente » Cod sursa (job #2188260) | Cod sursa (job #1331770) | Cod sursa (job #3257273) | Cod sursa (job #3290411) | Cod sursa (job #141933)
Cod sursa(job #141933)
using namespace std;
#include<cstdio>
#include<algorithm>
#define Nm (1<<16)
int A[Nm],B[Nm],C[Nm],L[Nm],R[Nm],H[Nm],P[Nm],h,n,t;
long long ans;
void read()
{
int i;
freopen("gardieni.in","r",stdin);
scanf("%d%d",&n,&t);
for(i=0;i<n;++i)
scanf("%d%d%d",A+i,B+i,C+i);
}
bool cmpl(int a, int b)
{
return A[a]<A[b];
}
bool cmpr(int a, int b)
{
return B[a]<B[b];
}
void sink(int x)
{
int v=H[x],son=x<<1;
while(son<=h)
{
if(son<h && C[H[son|1]]<C[H[son]])
son|=1;
if(C[v]<=C[H[son]])
break;
H[x]=H[son]; P[H[x]]=x;
x=son; son<<=1;
}
H[x]=v; P[v]=x;
}
void lift(int x)
{
int v=H[x];
while(x>1 && C[v]<C[H[x>>1]])
{
H[x]=H[x>>1];
P[H[x]]=x;
x>>=1;
}
H[x]=v; P[v]=x;
}
void solve()
{
int i,l=0,r=0;
for(i=0;i<n;++i)
L[i]=R[i]=i;
sort(L,L+n,cmpl);
sort(R,R+n,cmpr);
for(i=1;i<=t;++i)
{
while(h && B[R[r]]==i-1)
{
H[P[R[r]]]=H[h];
P[H[h--]]=P[R[r]];
lift(P[R[r]]);
sink(P[R[r]]);
++r;
}
while(l<n && A[L[l]]==i)
{
H[++h]=L[l];
P[L[l]]=h;
lift(h);
++l;
}
ans+=C[H[1]];
}
}
void write()
{
freopen("gardieni.out","w",stdout);
printf("%lld\n",ans);
}
int main()
{
read();
solve();
write();
return 0;
}