/**
* Note: The returned array must be malloced, assume caller calls free().
*/
struct list
{
struct list *next;
struct list *prev;
long x;
long x_h;
};
struct list head;
struct list end;
#define max(a, b) (a > b ? a : b)
int* fallingSquares(int** positions, int positionsSize,
int* positionsColSize, int* returnSize){
int *out;
int i;
out = (int *)malloc(sizeof(int) * positionsSize);
*returnSize = positionsSize;
head.next = &end;
head.x_h = 0;
head.x = 0;
end.prev = &head;
end.x = 2053500000;
printf("%d \n", end.x);
for (i = 0 ; i < positionsSize ; i++) {
out[i] = (int)inset(positions[i][0], positions[i][0] + positions[i][1]);
if (i > 0) out[i] = max(out[i - 1], out[i]);
}
return out;
}
int inset(int x, int x2)
{
struct list* s1;
struct list* s2;
struct list* s3;
long high = 0;
struct list *tmp = &head;
while (x > tmp->x) {
tmp = tmp->next;
}
if (x == tmp->x) {
s1 = tmp;
} else {
s1 = (struct list*)malloc(sizeof(struct list));
s1->x = x;
s1->x_h = tmp->prev->x_h;
s1->next = tmp;
s1->prev = tmp->prev;
tmp->prev->next = s1;
tmp->prev = s1;
}
tmp = &head;
while (x2 > tmp->x) {
tmp = tmp->next;
}
if (x2 == tmp->x) {
s2 = tmp;
} else {
s2 = (struct list*)malloc(sizeof(struct list));
s2->x = x2;
s2->x_h = tmp->prev->x_h;
s2->next = tmp;
s2->prev = tmp->prev;
tmp->prev->next = s2;
tmp->prev = s2;
}
high = s1->x_h;
while (s1->next != s2) {
high = max(high, s1->next->x_h);
s1->next->next->prev = s1;
s1->next = s1->next->next;
}
s1->x_h = high + x2 - x;
//printf("%d \n", s1->x_h);
return s1->x_h;
}
#define FOR(i, j) for (i = 0 ;i < j ;i++)
#define max(i, j) (i > j ? i : j)
int cmp(const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}
struct nd {
int profit;
int start;
int endl;
};
int cmp2(const void *a, const void *b)
{
return ((struct nd *)a)->endl - ((struct nd *)b)->endl;
}
int *g_buf;
int *g_max;
int g_cnt;
struct nd *g_node;
int jobScheduling(int* startTime, int startTimeSize,
int* endTime, int endTimeSize, int* profit, int profitSize)
{
int i;
int endcnt = 0;
int maxout = 0;
int temp;
g_cnt = startTimeSize;
g_buf = (int *)malloc(sizeof(int) * (startTimeSize + endTimeSize));
g_max = (int *)malloc(sizeof(int) * (startTimeSize + endTimeSize));
g_node = (struct nd *)malloc(sizeof(struct nd) * (startTimeSize + endTimeSize));
FOR(i, startTimeSize) {
g_buf[i] = startTime[i];
g_max[i] = 0;
g_node[i].start = startTime[i];
g_node[i].profit = profit[i];
g_node[i].endl = endTime[i];
}
FOR(i, endTimeSize) {
g_buf[i + startTimeSize] = endTime[i];
g_max[i + startTimeSize] = 0;
}
qsort(g_buf, startTimeSize + endTimeSize, sizeof(int), cmp);
qsort(g_node, startTimeSize, sizeof(struct nd), cmp2);
FOR(i, startTimeSize + endTimeSize) {
while (endcnt < startTimeSize && g_node[endcnt].endl <= g_buf[i]) {
temp = find(g_node[endcnt].start);
maxout = max(maxout, g_max[temp] + g_node[endcnt].profit);
endcnt++;
if (endcnt == startTimeSize) {break;}
}
g_max[i] = maxout;
}
printf("%d ", maxout);
return maxout;
}
int find(int num)
{
int min = 0;
int max = g_cnt << 1;
int j = g_cnt;
while (max - min > 1) {
if (g_buf[j] > num) {
max = j;
j = (min + max) / 2;
} else {
min = j;
j = (min + max) / 2;
}
}
return min;
}