I have been trying to solve this SPOJ problem R2D2.
I have been using segment tree.But I am getting TLE.Time limit is 7s. Constraints on input is following:
T <= 10
n <= 10^6
This is my code:(Constant factor is also significant)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
long int a[2000000],arr[2000000],seg[10000000][2];
char temp[20];
//Constructing segment tree.Storing array value in first column of seg[][] and array index in second column
long int ctrct(long int sb,long int se,long int si)
{
if(sb == se)
{
seg[si][0] = sb;
seg[si][1] = arr[sb];
}
else
{
long int mid = sb+(se-sb)/2;
long int l = ctrct(sb,mid,2*si+1);
long int r = ctrct(mid+1,se,2*si+2);
if(arr[l] >= arr[r])
{
seg[si][0] = l;
seg[si][1] = arr[l];
}
else
{
seg[si][0] = r;
seg[si][1] = arr[r];
}
}
return seg[si][0];
}
//getting maximum value in given range
long int getmax(long int ss,long int se,long int x,long int y,long int i)
{
if(ss >= x && se <= y)
{
return seg[i][0];
}
else if(ss > y || se <x)
return -1;
else
{
long int mid = (ss+se)/2;
long int l = getmax(ss,mid,x,y,2*i+1);
long int r = getmax(mid+1,se,x,y,2*i+2);
if(l == -1)
{
return r;
}
if(r == -1)
{
return l;
}
if(arr[l] >= arr[r])
return l;
else
return r;
}
}
void update(long int ss,long int se,long int x,long int val,long int i)
{
if(ss > x || se < x)
return;
if(ss != se)
{
long int mid = (ss+se)/2;
update(ss,mid,x,val,2*i+1);
update(mid+1,se,x,val,2*i+2);
if(seg[2*i+1][1] >= seg[2*i+2][1])
{
seg[i][1] = seg[2*i+1][1];
seg[i][0] = seg[2*i+1][0];
}
else
{
seg[i][1] = seg[2*i+2][1];
seg[i][0] = seg[2*i+2][0];
}
}
else
{
if(ss == x)
{
seg[i][1] = val;
seg[i][0] = x;
}
}
}
int main()
{
long int n,i,j,k,r,v,T,ans,l,segsize,pos,ctr;
scanf("%ld",&T);
while(T > 0)
{
fflush(stdin);
scanf("%ld",&k);
scanf("%ld",&n);
segsize = 2*(pow(2,ceil(log2(n))));
for(i=0;i<10000000;i++)
{
seg[i][0] = -1;
seg[i][1] = 0;
}
for(i=0;i<1000001;i++)
{
arr[i] = a[i] = 0;
}
std::cin.ignore(1);
for(i=0;i<n;i++)
{
gets(temp);
//Getting the input as per requirements
if(strlen(temp) > 3 && temp[1] == ' ' && (temp[2] >= 48 && temp[2] <= '57'))
{
l = 2;
r = 0;
v = 0;
while(temp[l] != ' ')
{
r = r*10 + (long int)(temp[l] - 48);
l++;
}
l++;
while(l < strlen(temp))
{
v = v*10 + (long int)(temp[l] - 48);
l++;
}
for(j=0;j<r;j++,i++)
{
a[i] = v;
arr[i] = k;
}
i--;
}
else
{
v = 0;
l = 0;
while(l < strlen(temp))
{
v = v*10 + (long int)(temp[l] - 48);
l++;
}
a[i] = v;
arr[i] = k;
}
}
ctrct(0,n-1,0);
ctr = 0;
for(i=0;i<n;i++)
{
pos = getmax(0,n-1,0,ctr,0);
//if for any index pos earlier than current max can fit the a[i] value than consider that position.Since always the first index of block is returned.
if(pos > 0 && arr[pos-1] >= a[i])
{
while(arr[pos-1] >= a[i])
{
pos = getmax(0,n-1,0,pos-1,0);
}
}
if(arr[pos] < a[i])
{
ctr++;
pos = getmax(0,n-1,0,ctr,0);
}
arr[pos] -= a[i];
update(0,n-1,pos,arr[pos],0);
}
ans = 0;
for(i = 0;i<=ctr;i++)
ans += arr[i];
printf("%ld %ld\n",(ctr+1),ans);
T--;
}
return 0;
}
Please suggest some better algorithm or some optimization.
**EDIT:**In the question we need to select the ship:(1)that can hold container(2)that has minimum index.
So I am using segment tree to get the maximum capacity left in the range 0 to no. of ship being used(range possibly consist of 0s and left over space).Since maximum possible may have index greater than “sufficient” capacity available, I am recursively checking from previous ranges leading to a constant factor(assuming (1)most containers are in block(2)tried without checking for previous ranges,did’nt get WA but TLE).
Since we need to update the ship capacity and get the ship index I am using a structure to store both the index and value of ship. So I am getting the required index and updating it.I tried it on extreme limits:
T = 10
n = 10^6
I got 16.263s on codeblocks.