Cod sursa(job #1435303)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 12 mai 2015 20:42:47
Problema Gardieni Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#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);
}