Speed Input Reading


JAVA

If you find that you are timing out using Java's native java.util.Scanner class consider using faster input reading.

A modified and much more performant version of the Scanner class can be copied from here.
Sample usage:

public class Main {
  // Paste Scanner class here.
  public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner();
    System.out.println(sc.nextInt());
  }
}

The java.io.BufferedReader is also much more performant than the native Scanner.
Sample usage of BufferedReader:

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    System.out.println(Integer.parseInt(reader.readLine()));
  }
}

Similarly, java.io.BufferedWriter can be used for faster output. Sample usage of BufferedWriter:

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);
    out.write(String.valueOf(100));
    out.write('\n');
    out.write("Hello, World!");
    out.flush();
  }
}

Improved Scanner

class FastIO {
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private DataOutputStream dout;
    private byte[] readBuffer;
    private byte[] writeBuffer;
    private int bufferPointer;
    private int bytesRead;
    private int pointer;
    public FastIO() {
        din = new DataInputStream(System.in);
        dout = new DataOutputStream(System.out);
        readBuffer = new byte[BUFFER_SIZE];
        writeBuffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
        pointer = 0;

    }
    public FastIO(String file_name) throws IOException {
        din = new DataInputStream(new FileInputStream(file_name));
        dout = new DataOutputStream(new FileOutputStream(file_name));
        writeBuffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
        pointer = 0;
    }
    public String readLine() throws IOException {
        byte[] buf = new byte[64];
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }
    public String nextString() throws IOException{

        // Skip all whitespace characters from the stream
        byte c = read();
        while(Character.isWhitespace(c)){
            c = read();
        }

        StringBuilder builder = new StringBuilder();
        builder.append((char)c);
        c = read();
        while(!Character.isWhitespace(c)){
            builder.append((char)c);
            c = read();
        }

        return builder.toString();
    }
    public int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }
    public int[] nextIntArray(int n) throws IOException {
        int arr[] = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = nextInt();
        }
        return arr;
    }
    public long nextLong() throws IOException {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }
    public long[] nextLongArray(int n) throws IOException {
        long arr[] = new long[n];
        for(int i = 0; i < n; i++){
            arr[i] = nextLong();
        }
        return arr;
    }
    public char nextChar() throws IOException{
        byte c = read();
        while(Character.isWhitespace(c)){
            c = read();
        }
        return (char) c;
    }
    public double nextDouble() throws IOException {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');

        if (c == '.') {
            while ((c = read()) >= '0' && c <= '9') {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }
    public double[] nextDoubleArray(int n) throws IOException {
        double arr[] = new double[n];
        for(int i = 0; i < n; i++){
            arr[i] = nextDouble();
        }
        return arr;
    }
    private void fillBuffer() throws IOException {
        bytesRead = din.read(readBuffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            writeBuffer[0] = -1;
    }
    private byte read() throws IOException {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return readBuffer[bufferPointer++];
    }

    public void close() throws IOException {
        if (din != null)
            din.close();
        if(dout != null)
            dout.close();
    }
    public void writeBytes(byte arr[]) throws IOException {

        int bytesToWrite = arr.length;

        if (pointer + bytesToWrite >= BUFFER_SIZE) {
            flush();
        }

        for (int i = 0; i < bytesToWrite; i++) {
            writeBuffer[pointer++] = arr[i];
        }
    }

    /**
     * NOTE: Need to call flush() when done!
     * @param str
     * @throws IOException
     */
    public void fastWrite(String str) throws IOException {
        writeBytes(str.getBytes());
    }
    /**
     * NOTE: Need to call flush() when done!
     * @param str
     * @throws IOException
     */
    public void fastWriteLine(String str) throws IOException {
        str+="\n";
        writeBytes(str.getBytes());
    }
    public void write(String str) throws IOException {
        writeBytes(str.getBytes());
        flush();
    }
    public void writeLine(String str) throws IOException {
        str+="\n";
        writeBytes(str.getBytes());
        flush();
    }
    public void flush() throws IOException {
        dout.write(writeBuffer, 0, pointer);
        dout.flush();
        pointer = 0;
    }
}

PYTHON

Python is also really slow. You can use the language pypy3 optimised for speed, but might memory overflow.

Try putting this at the top of your Python 3 code for a speed boost.

from sys import stdin
input = stdin.readline

Sample usage:

from sys import stdin
input = stdin.readline
x = input()