spoj.pl/problems/ACTIV/
Kindly please verify below DP code.
I think the DP solution is correct may be there is some issue wit output handling. I'm unable to point out the error.
#include <stdio.h>
#include <stdlib.h>
#define MAX(a,b) (a>b ? a:b)
unsigned long long DP[100001];
struct activities {
long s, e;
}a[100001];
int f (const void *a, const void *b)
{
return (((struct activities *)a)->s - ((struct activities *)b)->s);
}
int main ()
{
int n, i, j, lb, ub, mb;
unsigned long long v1, v2;
long e;
char ip[256];
while (1) {
gets (ip);
sscanf (ip, "%d", &n);
if (n==-1)
break;
for (i=0; i<n; i++) {
gets (ip);
sscanf (ip, "%ld %ld", &a[i].s, &a[i].e);
}
a[n].s = a[n].e = 1000000009;
qsort (a, n, sizeof(struct activities), f);
DP[n] = 0;
for (i=n-1; i>=0; i--) {
e = a[i].e;
v1 = DP[i+1];
lb = i;
ub = n;
mb = (lb+ub)/2;
while (ub-lb > 1) {
mb = (lb+ub) / 2;
if (a[mb].s == e)
break;
if (a[mb].s < e)
lb = mb+1;
else
ub = mb-1;
}
if (a[mb].s != e) {
for (j=lb; j<=n; j++) {
if (a[j].s >= e)
break;
}
mb = j;
}
v2 = DP[mb] + 1;
DP[i] = v1 + v2;
if (DP[i] >= 100000000)
DP[i] -= 100000000;
}
printf ("%08llu\n", DP[0]);
}
return 0;
}
Regards,
~ Ashish K.