Pagini recente » Cod sursa (job #303105) | Cod sursa (job #2464799) | Borderou de evaluare (job #1505655) | Cod sursa (job #576647) | Cod sursa (job #1615910)
#include <cstdio>
#define MAXN 50005
#define MAXT 1000000
bool ok[MAXN];
int n, heap[MAXN], v[MAXN], poz[MAXN], val[2*MAXN+1], m, next[2*MAXN+1], lista[MAXT+2];
inline void adauga(int x, int y){
m++;
val[m]=y;
next[m]=lista[x];
lista[x]=m;
}
inline int tata(int p){
return (p-1)/2;
}
inline int fiust(int p){
return 2*p+1;
}
inline int fiudr(int p){
return 2*p+2;
}
inline void swap(int a, int b){
int aux=heap[a];
heap[a]=heap[b];
heap[b]=aux;
poz[heap[a]]=a;
poz[heap[b]]=b;
}
inline void urcare(int p){
if(p>=n)return ;
while((p>0)&&(v[heap[p]]<v[heap[tata(p)]])){
swap(p, tata(p));
p=tata(p);
}
}
inline void coborare(int p){
int q, f=1;
while((f)&&(fiust(p)<n)){
q=fiust(p);
if((fiudr(p)<n)&&(v[heap[fiudr(p)]]<v[heap[q]])){
q=fiudr(p);
}
if(v[heap[q]]<v[heap[q]]){
swap(p, q);
p=q;
}else{
f=0;
}
}
}
int main(){
int k, t, i, a, b, p, x;
long long ans;
FILE *fin, *fout;
fin=fopen("gardieni.in", "r");
fout=fopen("gardieni.out", "w");
fscanf(fin, "%d%d", &k, &t);
for(i=0; i<k; i++){
fscanf(fin, "%d%d%d", &a, &b, &v[i]);
adauga(a, i);
adauga(b+1, i);
}
n=0;
ans=0;
for(i=1; i<=t; i++){
p=lista[i];
while(p){
if(ok[val[p]]){
n--;
x=heap[n];
heap[poz[val[p]]]=x;
poz[x]=poz[val[p]];
urcare(poz[x]);
coborare(poz[x]);
}else{
ok[val[p]]=1;
heap[n]=val[p];
poz[val[p]]=n;
n++;
urcare(n-1);
}
p=next[p];
}
ans+=v[heap[0]];
}
fprintf(fout, "%lld\n", ans);
fclose(fin);
fclose(fout);
return 0;
}