Untitled

package VocabSheet;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

class UserSolution {
	int num, n, m;
	TreeSet<Ele>[] all;
	TreeSet<Node>[] allocated;
	TreeSet<Node>[] empty; 
	int size;
	int[] max_per_section;
	
	HashMap<Integer, Node> hashMap;
	
	void display(){
		int[][] arr = new int[n][m];
		
		for(Integer key : hashMap.keySet()){
			Node node = hashMap.get(key);
			int r = node.idx/m;
			int c = node.idx%m;
			for(int i=0;i<node.len; i++){
				arr[r][c+i] = node.id;
			}
		}
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
		System.out.println("=====");
	}
	
	class Ele implements Comparable<Ele>{
		int id, idx, len, status;
		
		Ele(int mID, int mIdx, int mLen, int mStatus){
			id = mID;
			idx = mIdx;
			len = mLen;
			status = mStatus;
		}
		
		Ele(Node mNode, int mStatus){
			id = mNode.id;
			idx = mNode.idx;
			len = mNode.len;
			status = mStatus;
		}

		@Override
		public int compareTo(Ele o) {
			return idx -  o.idx;
		}
		
	}
	
	class Node implements Comparable<Node>{
		int id, idx, len;
		
		Node(int mID, int mIdx, int mLen){
			id = mID;
			idx = mIdx;
			len = mLen;
		}

		@Override
		public int compareTo(Node o) {
			if(len == o.len){
				return idx - o.idx;
			}
			return len - o.len;
		}
		
		
	}
	
	public void init(int N, int M)
	{
//		System.out.println("=====");
//		System.out.println(N+" "+M);
		size = (int) Math.sqrt(N);
		n = N;
		m = M;
		num = n/size;
		if(num*size < n) num++;
		hashMap = new HashMap<>();
		all = new TreeSet[num];
		allocated = new TreeSet[num];
		empty = new TreeSet[num]; 
		
//		System.out.println(n+" "+m+" "+num);
		for(int i=0; i<num; i++){
//			System.out.println("===");
			allocated[i] = new TreeSet<Node>();
			empty[i] = new TreeSet<Node>();
			all[i] = new TreeSet<Ele>();
			
			for(int j=i*size; j<Math.min((i+1)*size, n); j++){
//				System.out.println(j*m);
				empty[i].add(new Node(-1, j*m, m));
				all[i].add(new Ele(-1, j*m, m, 0));
			}
		}
		max_per_section = new int[num];
		Arrays.fill(max_per_section, m);
//		display();
	}

	public int writeWord(int mId, int mLen)
	{
//		System.out.println("write "+mId+" "+mLen);
		int idx = -1;
		for(int i=0; i<num; i++){
//			System.out.println(empty[i] == null);
			if(max_per_section[i] < mLen) continue;
//			node = empty[i].ceiling(new Node(mId, -1, mLen));
//			Node node = null;
//            int max = Integer.MAX_VALUE;
//            Iterator<Node> iterator = empty[i].descendingIterator();
//            while (iterator.hasNext()) {
//                Node tmp = iterator.next();
//                if(tmp.len < mLen) break;
//                if(tmp.idx < max){
//                    max = tmp.idx;
//                    node = tmp;
//                }
//            }
			Node node = null, node_;
            int len = mLen;
            do{
                node_ = empty[i].higher(new Node(mId, -1, len));
                if(node_ == null) break;
                if(node == null){
                    node = node_;
                } else if(node.idx > node_.idx){
                    node = node_;
                }
                len = node_.len+1;
            }while(node_ != null);
			
			if(node != null){
//				System.out.println(node.id+" "+node.idx+" "+node.len);
//				Node node = empty[i].ceiling(new Node(mId, -1, mLen));
				idx = node.idx;
				hashMap.put(mId, new Node(mId, node.idx, mLen));
				empty[i].remove(node);
				allocated[i].add(new Node(mId, node.idx, mLen));
				all[i].remove(new Ele(node, 0));
				all[i].add(new Ele(mId, node.idx, mLen, 1));
				if(node.len > mLen){
					
					all[i].add(new Ele(-1, node.idx+mLen, node.len-mLen, 0));
					empty[i].add(new Node(-1, idx+mLen, node.len-mLen));
				}else{
					all[i].add(new Ele(-1, node.idx, mLen, 0));
				}
//				System.out.println(idx/m);
//				display();
				if(empty[i].isEmpty()) max_per_section[i] = 0;
				else max_per_section[i] = empty[i].last().len; 
				return idx/m;
			}
		}
//		display();
		return idx;
	}

	public int eraseWord(int mId)
	{
//		System.out.println("erase "+mId);
		Node node = hashMap.remove(mId);
		if(node == null){
//			System.out.println(-1);
//			display();
			return -1;
		}
		for(int i=0; i<num; i++){
			if(allocated[i].contains(node)){
				allocated[i].remove(node);
				int new_idx = node.idx;
				int new_len = node.len;
				all[i].remove(new Ele(node, 1));
				Ele left = all[i].lower(new Ele(node, 0));
				Ele right = all[i].higher(new Ele(node, 0));
				if(left != null && left.idx/m == node.idx/m && left.status == 0){
					new_idx = left.idx;
					new_len = left.len + new_len;
					all[i].remove(left);
					empty[i].remove(new Node(-1, left.idx, left.len));
				}
				if(right != null && right.idx/m == node.idx/m && right.status == 0){
					new_len = new_len + right.len;
					all[i].remove(right);
					empty[i].remove(new Node(-1, right.idx, right.len));
				}
				all[i].add(new Ele(-1, new_idx, new_len, 0));
				empty[i].add(new Node(-1, new_idx, new_len));
//				System.out.println(node.idx/m);
//				display();
				if(empty[i].isEmpty()) max_per_section[i] = 0;
				else max_per_section[i] = empty[i].last().len; 
				return node.idx/m;
			}
		}
//		System.out.println(-1);
//		display();
		return -1;
	}

}