Pagini recente » Cod sursa (job #1145830) | Cod sursa (job #1306683) | Cod sursa (job #934416) | Cod sursa (job #2246840) | Cod sursa (job #1435303)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define inFile "gardieni.in"
#define outFile "gardieni.out"
#define MAX_N 50005
#define MAX_T 100000
ifstream in(inFile);
ofstream out(outFile);
unsigned short H[MAX_N + 1], nHeap;
int V[MAX_N + 1];
unsigned short P[MAX_N + 1];
vector < unsigned short > BEGIN[MAX_T + 1];
vector < unsigned short > END[MAX_T + 2];
void upHeap(unsigned short node);
void downHeap(unsigned short node);
void insHeap(unsigned short key);
void delHeap(unsigned short key);
int main() {
int N, T, i, j, A, B, cost = 0;
in >> N >> T;
for(i = 1; i <= N; i++) {
in >> A >> B >> V[i];
BEGIN[A].push_back(i);
END[B+1].push_back(i);
}
for(i = 1; i <= T; i++) {
for(j = 0; j < END[i].size(); j++)
delHeap(P[END[i][j]]);
for(j = 0; j < BEGIN[i].size(); j++)
insHeap(BEGIN[i][j]);
cost += V[H[1]];
}
out << cost << '\n';
return 0;
}
void upHeap(unsigned short node) {
int start = H[node];
while(node > 1 && V[start] < V[H[node/2]]) {
P[H[node/2]] = node;
H[node] = H[node/2];
node /= 2;
}
P[start] = node;
H[node] = start;
}
void downHeap(unsigned short node) {
int son;
do {
son = 0;
if(2*node <= nHeap) son = 2*node;
if(2*node+1 <= nHeap && V[H[2*node+1]] < V[H[son]]) son = 2*node+1;
if(V[H[node]] < V[H[son]]) son = 0;
if(son) {
P[H[son]] = node;
P[H[node]] = son;
swap(H[node], H[son]);
node = son;
}
} while(son);
}
void insHeap(unsigned short key) {
nHeap++;
P[key] = nHeap;
H[nHeap] = key;
upHeap(nHeap);
}
void delHeap(unsigned short key) {
P[H[nHeap]] = key;
H[key] = H[nHeap];
nHeap--;
if(key > 1 && V[H[key]] < V[H[key/2]]) upHeap(key);
else downHeap(key);
}