Untitled

public class UserSolution {
    int location = 30;
    int maxkey = 10000;
    int maxvalley = 50050;
     
    class hashkey {
        int count;
        int[] position = new int[location];
    }
     
    int n;
    int[] mp = new int[maxvalley];
    hashkey[] keys = new hashkey[maxkey];
     
    int createP(int x, int tH, int dir, int wL) {
        int x_l = x;
         
        int height_l = mp[x];
         
        mp[x] += tH;
         
        if (mp[x + dir] >= mp[x]) {
            mp[x_l] = height_l;
            return 0;
        }
         
        while (mp[x + dir] <= mp[x]) {
            x += dir;
        }
             
        int x1 = x, x2 = x, ret = 0;
         
        for (int y = mp[x] + 1; y <= mp[x_l]; y++) {
             
            while (mp[x2] < y) {
                if (mp[x2] > mp[x2 + dir]) {
                    mp[x_l] = height_l;
                    return ret;
                }
                x2 += dir;
            }
             
            while (mp[x1] < y) {
                if (mp[x1] > mp[x1 - dir]) {
                    mp[x_l] = height_l;
                    return ret;
                }
                x1 -= dir;
            }
             
            int water = (x1 > x2) ? (x1 - x2 - 1) : (x2 - x1 - 1);
                 
            if (ret + water > wL) {
                mp[x_l] = height_l;
                return ret;
            }
            ret += water;
        }
         
        mp[x_l] = height_l;
         
        return ret;
    }
     
    void init(int n, int[] mHeight) {
        this.n = n;
        mp[0] = mp[this.n - 1] = 150;
         
        for (int i = 0; i < maxkey; i++) {
            keys[i] = new hashkey();
            keys[i].count = 0;
        } 
         
        for (int h = 1; h < this.n - 1; h++) {
            mp[h] = mHeight[h];
             
            int key = 0;
             
            for (int i = 1; i < 5; i++) {
                 
                int d = mHeight[h] - mHeight[h + i] + 5;
                 
                if (d < 1 || d > 9) 
                    break;
                 
                key = (key * 10) + d;
                   
                if (i >= 2) {
                    if (keys[key].count >= location) 
                        keys[key].count++;
                    else
                        keys[key].position[keys[key].count++] = h;
                }
            }
        }
    }
     
    int countPosition(int mLen, int[] mTank) {
        int key = 0;
         
        for (int i = 1; i < mLen; i++) {
            int d = mTank[i] - mTank[0] + 5;
            key = (key * 10) + d;
        }
         
         
        return keys[key].count;
    }
     
    int buildAndPourOut(int mLen, int[] mTank, int mWater) {
        int key = 0;
         
        for (int i = 1; i < mLen; i++) {
            int d = mTank[i] - mTank[0] + 5;
            key = (key * 10) + d;
        }
         
        hashkey hash = keys[key];
         
        int answer = 0, puddle;
         
        for (int i = 0; i < hash.count; i++) {
            int currX = hash.position[i];
            
            puddle = createP(currX, mTank[0], -1, mWater);
             
            if (answer < puddle) 
                answer = puddle;
             
            
            puddle = createP(currX + mLen - 1, mTank[mLen - 1], 1, mWater);
             
            if (answer < puddle) 
                answer = puddle;
        }
         
        return answer;
    }
}

===
import java.util.*;
 
class UserSolution {
    HashMap<String, ArrayList<Integer>> map;
    int[] valley;
 
    void addtool(String h, int i){
        map.putIfAbsent(h, new ArrayList<>());
        map.get(h).add(i);
    }
 
    public void init(int N, int mHeight[]) {
        map = new HashMap<>();
        valley = new int[N];
        System.arraycopy(mHeight, 0, valley, 0, N);
 
        for(int i=1;i<N-4;i++){
            int[] local = new int[5];
            System.arraycopy(mHeight, i, local, 0, 5);
 
            int max3 = Math.max(Math.max(local[0], local[1]), local[2]);
            int min3 = Math.min(Math.min(local[0], local[1]), local[2]);
            int max4 = Math.max(max3, local[3]);
            int min4 = Math.min(min3, local[3]);
            int max5 = Math.max(max4, local[4]);
            int min5 = Math.min(min4, local[4]);
 
            if(max3 - min3 < 5) addtool("" + (max3 - local[0]) + (max3 - local[1]) + (max3 - local[2]), i);
 
            if(max4 - min4 < 5) addtool("" + (max4 - local[0]) + (max4 - local[1]) + (max4 - local[2]) + (max4 - local[3]), i);
 
            if(max5 - min5 < 5) addtool("" + (max5 - local[0]) + (max5 - local[1]) + (max5 - local[2]) + (max5 - local[3]) + (max5 - local[4]), i);
        }
 
        int max3 = Math.max(Math.max(mHeight[N-4], mHeight[N-3]), mHeight[N-2]);
        int min3 = Math.min(Math.min(mHeight[N-4], mHeight[N-3]), mHeight[N-2]);
 
        if(max3 - min3 < 5) addtool("" + (max3 - mHeight[N-4]) + (max3 - mHeight[N-3]) + (max3 - mHeight[N-2]), N-4);
    }
 
    public int countPosition(int mLen, int mTank[]) {
        int min = 5;
        for(int i=0;i<mLen;i++) min = Math.min(min, mTank[i]);
 
        StringBuilder hash = new StringBuilder();
        for(int i=0;i<mLen;i++) hash.append(mTank[i] - min);
 
        return map.get(hash.toString()).size();
    }
 
    public int buildAndPourOut(int mLen, int mTank[], int mWater) {
        int min = 5;
        for(int i=0;i<mLen;i++) min = Math.min(min, mTank[i]);
 
        StringBuilder hash = new StringBuilder();
        for(int i=0;i<mLen;i++) hash.append(mTank[i] - min);
 
        int answer = 0;
 
        for(int i : map.get(hash.toString())){
            answer = Math.max(answer, pour(i, valley[i] + mTank[0], mWater, -1));
            answer = Math.max(answer, pour(i + mLen - 1, valley[i] + mTank[0], mWater, 1));
        }
 
        return answer;
    }
 
    int pour(int loc, int height, int mount, int direction){
        if(valley[loc + direction] >= height) return 0;
 
        int original = valley[loc];
        valley[loc] = height;
 
        int answer = 0, low_left = loc + direction, low_right, layer, water_height;
 
        while(valley[low_left + direction] <= valley[low_left]) low_left += direction;
 
        low_right = low_left;
 
        while (valley[low_right - direction] == valley[low_right]) low_right -= direction;
 
        layer = Math.abs(low_right - low_left) + 1;
        water_height = valley[low_left];
 
        while (layer <= mount){
            answer += layer;
            mount -= layer;
            water_height++;
 
            if(water_height >= height) break;
 
            if(water_height >= valley[low_left + direction]){
                while (valley[low_left + direction] == water_height) low_left += direction;
                if(valley[low_left + direction] < water_height) break;
            }
 
            if(water_height >= valley[low_right - direction]){
                while (valley[low_right - direction] == water_height) low_right -= direction;
                if(valley[low_right - direction] < water_height) break;
            }
 
            layer = Math.abs(low_right - low_left) + 1;
        }
 
        valley[loc] = original;
        return answer;
    }
}

============
class UserSolution {
    class Shape {
        int count;
        int pos[];
 
        Shape(int index) {
            count = 1;
            pos = new int[30];
            pos[0] = index;
        }
    }
 
    int N;
    Shape[] list;
    int original[];
 
    int hash(int[] diff, int len) {
        int h = 0;
        for(int i = 0; i < len; i++){
            h = h*11+diff[i]+1;
        }
        return h;
    }
    void update(int h, int i){
        if(list[h]!=null){
            if(list[h].count >= 30){
                list[h].count++;
                list[h].pos = null;
            }else{
                list[h].pos[list[h].count]=i;                   
                list[h].count++;
            }
        }else{
            list[h] = new Shape(i);
        }
    }
    void hashShape(int[] map) {
        int temp[] = new int[4];
        int h=0;
        // W = 3;
        for (int i = 1; i <= N - 4; i++) {
            temp[0] = map[i]-map[i+1]+4;
            temp[1] = map[i]-map[i+2]+4;
            if(temp[0] < 0 || temp[1] < 0 ||temp[0] > 10 || temp[1] > 10) continue;
            h = hash(temp, 2);
            update(h, i);
        }
        // W = 4;
        for (int i = 1; i <= N - 5; i++) {
            temp[0] = map[i]-map[i+1]+4;
            temp[1] = map[i]-map[i+2]+4;
            temp[2] = map[i]-map[i+3]+4;
            if(temp[0] < 0 || temp[1] < 0 ||temp[0] > 10 || temp[1] > 10 || temp[2] < 0|| temp[2] > 10) continue;
            h = hash(temp, 3);
            update(h, i);
        }
        // W = 5;
        for (int i = 1; i <= N - 6; i++) {
            temp[0] = map[i]-map[i+1]+4;
            temp[1] = map[i]-map[i+2]+4;
            temp[2] = map[i]-map[i+3]+4;
            temp[3] = map[i]-map[i+4]+4;
            if(temp[0] < 0 || temp[1] < 0 ||temp[0] > 10 || temp[1] > 10 || temp[2] < 0|| temp[2] > 10
                    || temp[3] < 0|| temp[3] > 10) continue;
            h = hash(temp, 4);
            update(h, i);
        }
    }
    // 3 * 50000 = 15000;
    public void init(int N, int mHeight[]) {
        this.N = N;
        list = new Shape[15000];
        hashShape(mHeight);
        original = mHeight;
    }
    // 1 * 100000
    public int countPosition(int mLen, int mTank[]) {
        int temp[] = new int[4];
        int h;
        for(int i = 0; i < mLen-1; i++){
            temp[i] = mTank[i+1]-mTank[0]+4;
        }
        h = hash(temp, mLen-1);
        return list[h].count;
    }
    // 500 * 30* 2 * 500 =   15*10^6
    public int buildAndPourOut(int mLen, int mTank[], int mWater) {
        int temp[] = new int[4];
        int h;
        for(int i = 0; i < mLen-1; i++){
            temp[i] = mTank[i+1]-mTank[0]+4;
        }
        h = hash(temp, mLen-1);
        int ret = 0;
        int curr, tankHeight, index;
        for(int i = 0; i < list[h].count; i++){
            index = list[h].pos[i];
            tankHeight = original[index]+mTank[0];
            curr = calcFromIndex(index, -1, mWater, tankHeight);
            if(curr > ret) ret = curr;
             
            curr = calcFromIndex(index+mLen-1, 1, mWater, tankHeight);
            if(curr > ret) ret = curr;
        }
        return ret;
    }
    int calcFromIndex(int index, int dir, int mWater, int tankHeight){
        if(original[index+dir] >= tankHeight) return 0;
        int oldHeight = original[index];
        original[index]=tankHeight;
         
        int puddle =  index +dir;
        while(original[puddle] >= original[puddle+dir]) puddle += dir;
        int ret = spread(puddle, tankHeight, mWater);
        original[index]=oldHeight;
        return ret;
    }
    int spread(int curr, int maxHeight, int mWater){
        int totalAmount = 0;
        int curAmount = 0;
        int left = curr, right = curr;
        for(int i = original[curr]; i < maxHeight; i++){
            while(original[left] == i){
                if(original[left-1] < original[left]) return totalAmount;
                left--;
            }
            while(original[right] == i){
                if(original[right+1] < original[right]) return totalAmount;
                right++;
            }
            curAmount = right - left - 1;
            if(totalAmount+curAmount > mWater) break;
            totalAmount+=curAmount;
        }
        return totalAmount;
    }
}