Pagini recente » Cod sursa (job #2311719) | Cod sursa (job #1078034) | Cod sursa (job #1547318) | Cod sursa (job #2405107) | Cod sursa (job #1615915)
#include <cstdio>
#include <cctype>
#define BUF_SIZE 4096
#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];
int pos=BUF_SIZE;
char buf[BUF_SIZE];
FILE *fin;
inline char nextch(){
if(pos==BUF_SIZE){
fread(buf, BUF_SIZE, 1, fin);
pos=0;
}
return buf[pos++];
}
inline int read(){
int x=0;
char ch=nextch();
while(!isdigit(ch)){
ch=nextch();
}
while(isdigit(ch)){
x=10*x+ch-'0';
ch=nextch();
}
return x;
}
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[p]]){
swap(p, q);
p=q;
}else{
f=0;
}
}
}
int main(){
int k, t, i, a, b, p, x;
long long ans;
FILE *fout;
fin=fopen("gardieni.in", "r");
fout=fopen("gardieni.out", "w");
k=read();
t=read();
for(i=0; i<k; i++){
a=read();
b=read();
v[i]=read();
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;
}