JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
spoj INVCNT | Reply
I am trying to solve spoj INVCNT (http://www.spoj.com/problems/INVCNT/) using BIT.using the approach given here http://apps.topcoder.com/forums/?module=Thread&threadID=710471&start=0&mc=8#1688420 . However using the compression technique, i am getting TLE and w/o compression i am getting NZEC error in java. Here's my code :-
import java.io.IOException;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.io.PrintStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.InputStream;
 
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastReader in = new FastReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		INVCNT solver = new INVCNT();
		solver.solve(1, in, out);
		out.close();
	}
}
 
class INVCNT
{
    class Number  implements Comparable<Number>
    {
        long num;
        int index;
        public Number(long i1, int i)
        {
               num = i1;
            index = i;
        }
 
        public int compareTo(Number o)
        {
            return Long.valueOf(num).compareTo(o.num);
        }
    }
 
    public void solve(int testNumber, FastReader in, PrintWriter out)
    {
       //int maxVal = 10000000;
        int t = in.nextInt();
        while (t-->0)
        {
            int n = in.nextInt();
 
            Number a[] = new Number[n];
            for(int i = 0; i<n; i++)
            {
                a[i] = new Number(in.nextLong(), i);
            }
            Arrays.sort(a);
            /* using Compressing technique
            */
            int b[] = new int[n];
            for(int i = 1; i<=n; i++)
            {
                b[a[i-1].index] = i;
            }
            BIT bit = new BIT(n);
            long inv = 0;
            for(int i = 0; i<n; i++)
            {
                int x = b[i];
                long elemGreaterThanX = bit.getCF(n) - bit.getCF(x);
                inv += elemGreaterThanX;
                bit.updateF(x,1);
            }
            out.println(inv);
        }
    }
}
 
class FastReader
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    
    public FastReader(InputStream stream)
    {
        this.stream = stream;
    }
    
    public int next()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read(buf);
            } catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
    
    public int nextInt()
    {
        int c = next();
        while (isSpaceChar(c))
            c = next();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = next();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = next();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    
    public String nextString()
    {
        int c = next();
        while (isSpaceChar(c))
            c = next();
        StringBuffer res = new StringBuffer();
        do
        {
            res.appendCodePoint(c);
            c = next();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    
    public Long nextLong()
    {
        return Long.parseLong(nextString());
    }
    
    public static boolean isSpaceChar(int c)
    {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
}
 
class BIT
{
    public int n;
    public int tree[]; // stores partial cf
    public int f[]; // stores individual freq, for fast access we store them
 
    public BIT(int n)
    {
        this.n = n;
        tree = new int[n + 1]; // 1 based index
        f = new int[n+1];
        f[0] = tree[0]=0;
    }
 
    private int getLastElementsStored(int idx)
    {
        return idx & (-idx);
    }
    public int getCF(int idx) // get cumulative freq for index i
    {
        if(idx > n)
            idx = n;
        if(idx<1)
            return 0;
        int sum = 0;
        while (idx > 0)
        {
            sum += tree[idx];
            idx -= getLastElementsStored(idx);
        }
        return sum;
    }    
    public void updateF(int idx, int incr)
    {
        if(idx < 1)
            throw new IllegalArgumentException();
        f[idx]+=incr;
        while(idx<=n)
        {
            tree[idx]+=incr;
            idx += getLastElementsStored(idx);
        }
    }
    
   }
 


So what should i do to get AC?
RSS