import java.util.*; /** * Use Sqrt Decomposition. * Instead of trying to keep track of the length of mountain segments, keep * track of how much of the x axis is covered, then multiply by sqrt(2). * * In each block in the sqrt decomposition we keep track of how many mountains * cover a particular segment of the x axis. For each block we also keep track * of a total of how much of the block is covered and how many mountain segments * fully cover the entire block. Since w is up to 10^9, use coordinate compression * and only keep track of the points that are actually used. * * Time complexity: O(3*q*sqrt(2*q)) * * @author Finn Lidbetter */ public class mountaincraft_finn { static int blockSize = 1; static int numBlocks = 1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int q = sc.nextInt(); long w = sc.nextInt(); long[] x = new long[q]; long[] y = new long[q]; long[] keyPoints = new long[2*q+2]; double rt2 = Math.sqrt(2.0); for (int i=0; i pointToIndex = new HashMap<>(); ArrayList indexToPoint = new ArrayList<>(); long prev = Long.MIN_VALUE; int index = 0; for (long k: keyPoints) { if (k>=0 && k<=w && k!=prev) { pointToIndex.put(k,index); indexToPoint.add(k); index++; } prev = k; } int numVals = indexToPoint.size(); int sqrt = (int)Math.sqrt(numVals); blockSize = sqrt; numBlocks = numVals / blockSize; if (blockSize*numBlocks < numVals) { numBlocks++; } int[] blockValues = new int[numBlocks]; int[][] individualCounts = new int[numBlocks][blockSize]; long[] blockWidth = new long[numBlocks]; int[] fullyCovered = new int[numBlocks]; for (int i=0; i active = new HashSet<>(); for (int t=0; tw) { rightPoint = w; } int leftIndex = pointToIndex.get(leftPoint); int rightIndex = pointToIndex.get(rightPoint); int leftBlock = getBlock(leftIndex); int leftOffset = getOffset(leftIndex); int rightBlock = getBlock(rightIndex); int rightOffset = getOffset(rightIndex); for (int block = leftBlock+1; block 0) { querySum += blockWidth[block]; } else { querySum += blockValues[block]; } } System.out.println(querySum*rt2); } } static int getBlock(int index) { return index / blockSize; } static int getOffset(int index) { return index % blockSize; } } class Pair { long x,y; public Pair(long xx, long yy) { x = xx; y = yy; } public boolean equals(Object obj) { Pair p2 = (Pair) obj; return x==p2.x && y==p2.y; } public int hashCode() { return Objects.hash(x,y); } }