Problem_12356.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
import static java.lang.System.out;

/**
 * TLE !! 
 * Algorithm is correct. use buffered read/writer instead for faster performance 
 * 
 * full implementation using buffered IO here: http://ideone.com/U8rcHV
 */
public class Main {

  public static void main(String[] args) {
		
		
		 
		Scanner in = new Scanner(System.in);
    	 while(in.hasNext()) {
    		 
    		 int numSoldiers = in.nextInt();
    		 if(numSoldiers == 0) break; 
    		 
    		 // Simple doubly linked list using array. L[i] gives the LHS of element i 
    		 // we can have a int[] content as well to give the content (if any) of element i; 
    		 // disadvantage of this is that memory isnt free up
    		 int[] L = new int[numSoldiers+22];	
    		 int[] R = new int[numSoldiers+22];
    		 
    		 final int NIL = 0; 
    		 
    		 L[0] = R[0] = NIL;
    		 for(int i=1; i<=numSoldiers; ++i) {
    			L[i] = i - 1;
	            R[i] = i + 1;
    		 }
    		 
    		 R[numSoldiers] = NIL; 
    		 
    		 int loss = in.nextInt(); 
    		 
    		 int lhs, rhs, sL, sR;	 //sL = survivor	 
    		 for(int i=0; i<loss; i++) {
    	   		 lhs =  in.nextInt(); 
        		 rhs =  in.nextInt();
        		 
        		 sL = L[lhs]; 
        		 sR = R[rhs]; 
        		  
        		 if(sL == NIL && sR == NIL)
        			 out.println("* *");
        		 
    			 if(sL == NIL && sR != NIL)
        			 out.println("* " + sR);
    			 
        		 if(sL != NIL && sR == NIL)
        			 out.println(sL + " *");
        		 
        		 if(sL != NIL && sR != NIL)
        			 out.println(sL + " " + sR); 
        		 
        		 R[sL] = sR;
        		 L[sR] = sL;
        
    		 }
    		 
    		 out.println("-");
    		 
    	 }
    	 
		
	}//end of void main 
}//end of class main 




//////////////
// here's another implementation using arrays instead of linked list. 
//import java.io.BufferedReader;
//import java.io.IOException;
//import java.io.InputStreamReader;
//import java.util.Arrays;
//import java.util.HashMap;
//import java.util.Scanner;
//import static java.lang.System.out;
//
///**
// * 2pm 
// */
//public class Main {
//
//	public static void main(String[] args) {
//		
//		
//		 
//		Scanner in = new Scanner(System.in);
//    	 while(in.hasNext()) {
//    		 
//    		 int numSoldiers = in.nextInt();
//    		 if(numSoldiers == 0) break; 
//    		 
//    		 int loss = in.nextInt(); 
//    		 int[] soldiers = new int[numSoldiers +1];
//    		 final int dead = -1; 
//    		 final int NIL = Integer.MIN_VALUE;
//		 	 int[][] kills = new int[numSoldiers +1][2]; //to jump array
//
//    		 soldiers[0] = NIL; //sentinel
// 
//    		 int L, R; //sL = survivor Left 
//    		
//    		 for(int i=0; i<loss; i++) {
//    	   		 L =  in.nextInt(); 
//        		 R =  in.nextInt();
//        		 int sL = NIL, sR = NIL;
//        		 
//        		 
//        		 //kill from left to right 
//        		 for(int k=L; k<=R; k++) {
//        			 soldiers[k] = dead; 
//        			 kills[k][0] = L-1;
//        			 kills[k][1] = R+1;
//        		 }
//        		 
//        		 //out.println("LK: " + L + " RK: " + R);
//        		 // get survivors 
//        		 for(int k=L; k>0; k--) {
//        			 //out.println("left" + k);
//        			 //if(k == 1) break;
//        			 if(soldiers[k] != dead){
//        				 sL = k;
//        				 break; 
//        			 }else { 
//        				k = kills[k][0] +1;
//        			 }
//        		 }
//        		 
//        		 for(int k=R; k<=numSoldiers; k++) {
//        			 //if(k==numSoldiers) break; 
//        			 if(soldiers[k] != dead){
//        				 sR = k;
//        				 break; 
//        			 }else {
//        				 k = kills[k][1] -1; 
//        				
//        			 }
//        		 }
//        		 
//        		 if(sL == NIL && sR == NIL)
//        			 out.println("* *");
//        		 
//    			 if(sL == NIL && sR != NIL)
//        			 out.println("* " + sR);
//    			 
//        		 if(sL != NIL && sR == NIL)
//        			 out.println(sL + " *");
//        		 
//        		 if(sL != NIL && sR != NIL)
//        			 out.println(sL + " " + sR); 
//    		 }
//    		 
//    		 out.println("-");
//    		 
//    	 }
//    	 
//		
//	}//end of void main 
//}//end of class main