Pagini recente » Cod sursa (job #1436263) | Cod sursa (job #1286485) | Cod sursa (job #2415482) | Cod sursa (job #2263004) | Cod sursa (job #305881)
Cod sursa(job #305881)
#include <iostream>
FILE *f = fopen("heavymetal.in", "r"), *g = fopen("heavymetal.out", "w");
using namespace std;
int *a, *b, *heapA, *heapB, N, *timp, *maxim;
int swap(int k, int p)
{
int aux = heapA[k];
heapA[k] = heapA[p];
heapA[p] = aux;
aux = heapB[k];
heapB[k] = heapB[p];
heapB[p] = aux;
return 0;
}
int addHeap(const int x, const int y, int k)
{
heapA[k] = x;
heapB[k] = y;
while (heapB[(k - 1) / 2] > heapB[k])
{
swap(k, (k - 1) / 2);
k = (k - 1) / 2;
}
return 0;
}
int deleteHeap(int k)
{
a[k] = heapA[0];
b[k] = heapB[0];
int nrElemente = N - 1 - k;
heapA[0] = heapA[nrElemente];
heapB[0] = heapB[nrElemente];
nrElemente--;
k = 0;
while ((2 * k + 2 <= nrElemente) && ((heapB[k] > heapB[2 * k + 1]) || (heapB[k] > heapB[2 * k + 2])))
{
if ((heapB[k] > heapB[2 * k + 1]) && (heapB[k] > heapB[2 * k + 2]))
{
if (heapB[2 * k + 1] > heapB[2 * k + 2])
{
swap(k , 2 * k + 2);
k = 2 * k + 2;
}
else
{
swap(k, 2 * k + 1);
k = 2 * k + 1;
}
}
else
{
if (heapB[k] > heapB[2 * k + 1])
{
swap(k, 2 * k + 1);
k = 2 * k + 1;
}
else
{
swap(k, 2 * k + 2);
k = 2 * k + 2;
}
}
}
if ((2 * k + 1 <= nrElemente) && (heapB[k] > heapB[2 * k + 1]))
{
swap(k, 2 * k + 1);
}
return 0;
}
int cautareBinara(int total, int val)
{
int li = 0, ls = total;
while (li < ls)
{
int m = (li + ls) / 2;
if (timp[m] == val)
{
return maxim[m];
}
else
{
if (timp[m] < val)
{
li = m + 1;
}
else
{
ls = m - 1;
}
}
}
if (timp[li] == val) return maxim[li];
if (timp[li] < val) return maxim[li + 1];
if (timp[li] > val) return maxim[li - 1];
}
int main()
{
fscanf(f, "%d", &N);
a = new int[N];
b = new int[N];
heapA = new int[N];
heapB = new int[N];
for (int i = 0; i < N; ++i)
{
int x, y;
fscanf(f, "%d %d", &x, &y);
addHeap(x, y, i);
}
fclose(f);
for (int i = 0; i < N; ++i)
{
deleteHeap(i);
}
delete[] heapA;
delete[] heapB;
timp = new int[N];
maxim = new int[N];
int j = 0, m = 0;
while (a[j] == a[0])
{
if (m < b[j] - a[j])
{
m = b[j] - a[j];
}
j++;
}
int nr = 0; // numarul de elemente din timp si max;
timp[nr] = a[0];
maxim[nr] = m;
for (int i = j; i < N; ++i)
{
if (a[i] < timp[0])
{
if (timp[nr] != b[i])
{
timp[++nr] = b[i];
maxim[nr] = b[i] - a[i];
}
else
{
if (maxim[nr] < b[i] - a[i])
{
maxim[nr] = b[i] - a[i];
}
}
}
else
{
int t = cautareBinara(nr, a[i]); //returneaza val maxima a timpului cel mai apropiat de a[i]
if (timp[nr] != b[i])
{
timp[++nr] = b[i];
maxim[nr] = t + b[i] - a[i];
}
else
{
if (maxim[nr] < b[i] - a[i] + t)
{
maxim[nr] = b[i] - a[i] + t;
}
}
}
}
fprintf(g, "%d", maxim[nr]);
fclose(g);
delete[] timp;
delete[] maxim;
delete[] a;
delete[] b;
return 0;
}