fork(1) download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Main
  6. {
  7. 	static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  8. 	static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
  9.  
  10. 	static int n, h, b, e;
  11. 	static int[] c;
  12. 	static int[] res;
  13. 	static int[][] m;
  14.  
  15. 	static void sparse_table(int n) {
  16. 		for (int i = 0; i < n; i++) {
  17. 			m[i][0] = i;
  18. 		}
  19.  
  20. 		for (int j = 1; 1 << j <= n; j++) {
  21. 			for (int i = 0; i + (1 << j) - 1 < n; i++) {
  22. 				if (c[m[i][j-1]] < c[m[i + (1 << (j - 1))][j-1]]) {
  23. 					m[i][j] = m[i][j-1];
  24. 				} else if (c[m[i + (1 << (j - 1))][j-1]] < c[m[i][j-1]]) {
  25. 					m[i][j] = m[i + (1 << (j - 1))][j-1];
  26. 				} else {
  27. 					m[i][j] = m[i][j-1];
  28. 				}
  29. 			}
  30. 		}
  31. 	}
  32.  
  33. 	/*
  34. 	 * Returns first minimum 
  35. 	 */
  36. 	static int query_spares_table(int i, int j) {
  37. 		if (j > c.length) {
  38. 			j = c.length;
  39. 		}
  40. 		int log = log2(j - i + 1);
  41.  
  42. 		if (c[m[i][log]] <= c[m[j - (1 << log) + 1][log]]) {
  43. 			return m[i][log];
  44. 		} else {
  45. 			return m[j - (1 << log) + 1][log];
  46. 		}
  47. 	}
  48.  
  49. 	static int log2(int n) {
  50. 		return Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
  51. 	}
  52.  
  53. 	static String process() throws Exception {
  54. 		int runner = b-1;
  55. 		int[] res = new int[e - b + 1];
  56. 		int i = 0, bought = runner-1;
  57. 		while (runner < e) {
  58. 			int nextToBuy = runner + h - 1 > e - 1 ? e - 1 : runner + h - 1;
  59. 			while (nextToBuy != runner && c[query_spares_table(runner + 1, nextToBuy)] <= c[runner]) {
  60. 				nextToBuy = query_spares_table(runner+1, nextToBuy) - 1;
  61. 			}
  62. 			if (nextToBuy > bought) {
  63. 				if (nextToBuy == runner) {
  64. 					res[i] = 1;
  65. 					bought++;
  66. 				} else {
  67. 					res[i] += nextToBuy - bought;
  68. 					bought = nextToBuy;
  69. 				}
  70. 			}
  71. 			i++;
  72. 			runner++;
  73. 		}
  74. 		StringBuilder builder = new StringBuilder();
  75. 		boolean start = true;
  76. 		for (int r: res) {
  77. 			if (start) {
  78. 				builder.append(r);
  79. 			} else {
  80. 				builder.append("\t");
  81. 				builder.append(r);
  82. 			}
  83. 			start = false;
  84. 		}
  85. 		return builder.toString();
  86. 	}
  87.  
  88. 	public static void main(String[] args) throws Exception {
  89. 		//		writer = new BufferedWriter(new FileWriter("output.txt"));
  90. 		String input, data[];
  91. 		while ((input = reader.readLine()) != null) {
  92. 			while (input.equals("")) {
  93. 				input = reader.readLine();
  94. 			}
  95. 			data = input.split("\\s+");
  96. 			n = Integer.parseInt(data[0]); h = Integer.parseInt(data[1]);
  97. 			b = Integer.parseInt(data[2]); e = Integer.parseInt(data[3]);
  98. 			input = reader.readLine();
  99. 			while (input.equals("")) {
  100. 				input = reader.readLine();
  101. 			}
  102. 			c = Arrays.asList(input.split("\\s+")).stream().mapToInt(Integer::parseInt).toArray();
  103. 			m = new int[n+1][log2(n) + 1];
  104. 			sparse_table(n);
  105. 			writer.write(String.format("%s", process()));
  106. 			writer.newLine();
  107. //			writer.flush();
  108. 		}
  109. 		writer.close();
  110. 		reader.close();
  111. 	}
  112. }
Success #stdin #stdout 0.12s 35016KB
comments (?)
stdin
copy 
7 4 1 7
5 2 3 4 2 5 6
11 1 1 11
5 2 3 4 2 1 1 2 5 6 5
11 2 1 11
5 2 3 4 2 1 1 2 5 6 5
stdout
copy 
1	3	0	0	3	0	0
1	1	1	1	1	1	1	1	1	1	1
1	2	1	0	1	1	2	1	1	0	1
https://ideone.com/svjFC5
problem TNVFC1M, based on SPOJ submission 25650405 (JAVA), 2020-03-29 11:46:16
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!