Pagini recente » Cod sursa (job #1160736) | Cod sursa (job #196295) | Cod sursa (job #1076695) | Cod sursa (job #2717) | Cod sursa (job #1513231)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_VALUE 2147483648
#define MAX_RAND 524287
#define MAX_SIZE 300000
#define Nadejde 100000
#define MAX_LEVEL 20
typedef struct {
int v, time;
} cell;
typedef struct {
int v, next;
} list;
int *adj, inside;
int level, bufPtr;
int N, L, X, buff;
cell save[Nadejde]; // vectorul de intrare modificat.
list l[Nadejde + 1]; // lista cu lana oilor.
int update[MAX_LEVEL]; // folosit in timpul inserarii.
unsigned int sl[MAX_SIZE]; // zona de memorie prealocata.
/** Aloca-mi un vector de "size" + 1 elemente. **/
void alloc(int size) {
adj = (int*)calloc(size + 1, sizeof(int));
}
/** Initializeaza structura. **/
void init() {
sl[0] = -MAX_VALUE;
sl[MAX_LEVEL + 1] = MAX_VALUE;
int l;
for (l = 1; l <= MAX_LEVEL; l++) {
sl[l] = MAX_LEVEL + 1;
}
level = 1;
bufPtr = MAX_LEVEL + 2;
}
/** Da-mi un nivel random. **/
int randomLevel() {
int r, l = 0;
for (r = rand() & MAX_RAND; r; r >>= 1) {
l++;
}
return l;
}
/** Adauga la lista "pos" valoarea "val". **/
void add(int pos, int val) {
l[++buff].v = val;
l[buff].next = adj[pos];
adj[pos] = buff;
}
/** Insereaza in structura valoarea "x". **/
void insert(int x) {
int l, pos = 0;
for (l = level - 1; l >= 0; l--) {
while (sl[sl[pos + l + 1]] < x) {
pos = sl[pos + l + 1];
}
update[l] = pos;
}
int newLevel = randomLevel();
if (newLevel > level) {
for (l = level; l < newLevel; l++) {
update[l] = 0;
}
level = newLevel;
}
sl[bufPtr] = x;
for (l = 0; l < newLevel; l++) {
sl[bufPtr + l + 1] = sl[update[l] + l + 1];
sl[update[l] + l + 1] = bufPtr;
}
bufPtr += newLevel + 1;
inside++;
}
/** Sterge din structura valoarea "x". **/
void erase(int x) {
int l, pos = 0;
for (l = level - 1; l >= 0; l--) {
while (sl[sl[pos + l + 1]] < x) {
pos = sl[pos + l + 1];
}
update[l] = pos;
}
pos = sl[pos + 1];
l = 0;
while ((l < level) && (sl[update[l] + l + 1] == pos)) {
sl[update[l] + l + 1] = sl[pos + l + 1];
l++;
}
inside--;
}
/** Da-mi elementul maxim din structura. **/
int maxHeap() {
int l, val, pos = 0;
for (l = level - 1; l >= 0; l--) {
while (sl[sl[pos + l + 1]] < MAX_VALUE) {
pos = sl[pos + l + 1];
}
}
val = sl[pos];
erase(val);
return val;
}
int main(void) {
srand(time(NULL));
long long int sum = 0;
int i, val, pos, dist, max = 0;
FILE *f = fopen("lupu.in", "r");
init();
/* Citeste caracteristicile oilor. **/
fscanf(f, "%d %d %d", &N, &X, &L);
for (i = 0; i < N; i++) {
fscanf(f, "%d %d", &dist, &save[i].v);
if (dist <= X) {
save[i].time = (X - dist) / L + 1;
if (save[i].time > max) {
max = save[i].time;
}
}
}
fclose(f);
f = fopen("lupu.out", "w");
alloc(max);
/* Adauga in lista structura "save". */
for (i = 0; i < N; i++) {
if (save[i].time) {
add(save[i].time, save[i].v);
}
}
/* Calculeaza cantitatea maxima de lana pe care o poate obtine lupul. */
for (i = max; i > 0; i--) {
if (adj[i]) {
for (pos = adj[i]; pos; pos = l[pos].next) {
insert(l[pos].v);
}
}
if (inside) {
sum += maxHeap();
}
}
fprintf(f, "%lld\n", sum);
fclose(f);
/// Multumim Doamne!
puts("Doamne ajuta!");
return 0;
}