fork download
copy 
  1. import java.io.IOException;
  2. import java.io.InputStream;
  3. import java.io.PrintWriter;
  4. import java.util.InputMismatchException;
  5.  
  6. class FREQUENT {
  7. 	static int n;
  8.  
  9. 	public static void main(String[] args) {
  10. 		InputReader s = new InputReader(System.in);
  11. 		PrintWriter w = new PrintWriter(System.out);
  12. 		n = s.nextInt();
  13. 		while (true) {
  14. 			int q = s.nextInt();
  15. 			long[] a = new long[n];
  16. 			long count = 0, num = Integer.MAX_VALUE;
  17. 			for (int i = 0; i < n; i++) {
  18. 				a[i] = s.nextLong();
  19. 				if (a[i] != num) {
  20. 					count++;
  21. 					num = a[i];
  22. 				}
  23. 			}
  24. 			num = a[0];
  25. 			long[] left = new long[(int) count];
  26. 			long[] right = new long[(int) count];
  27. 			long[] pre_tree = new long[(int) count];
  28. 			left[0] = 0;
  29. 			int index = 0;
  30. 			count = 1;
  31. 			for (int i = 0; i < n - 1; i++) {
  32. 				if (a[i] == a[i + 1])
  33. 					count++;
  34. 				else {
  35. 					// count++;
  36. 					pre_tree[index] = count;
  37. 					count = 1;
  38. 					right[index] = i;
  39. 					left[++index] = i + 1;
  40. 				}
  41.  
  42. 			}
  43. 			pre_tree[index] = count;
  44.  
  45. 			count = 1;
  46. 			right[index] = a.length - 1;
  47. 			long tree[];
  48. 			int temp = pre_tree.length;
  49. 			if ((temp & (temp - 1)) == 0)
  50. 				tree = new long[2 * temp - 1];
  51. 			else {
  52. 				temp = (int) (Math.log(temp) / Math.log(2));
  53. 				temp++;
  54. 				temp = 1 << temp;
  55. 				tree = new long[2 * temp - 1];
  56.  
  57. 			}
  58. 			for (int i = 0; i < tree.length; i++) {
  59. 				tree[i] = (Integer.MIN_VALUE);
  60. 			}
  61. 			make_tree(pre_tree, tree, 0, pre_tree.length - 1, 0);
  62. 			while (q-- > 0) {
  63. 				long l = s.nextLong(), r = s.nextLong();
  64. 				l--;
  65. 				r--;
  66. 				long ans = 0;
  67. 				int ql = binarySearch(left, l);
  68. 				int qr = binarySearch(right, r);
  69. 				if (qr == -1) {
  70. 					ans = r - l + 1;
  71. 				} else if (left[ql] != l && right[qr] != r) {
  72.  
  73. 					long max1 = l - right[ql] + 1, max3 = r - left[qr + 1] + 1;
  74. 					long max2 = query(tree, ql + 1, qr, 0, pre_tree.length - 1, 0);
  75. 					ans = Math.max(Math.max(max1, max2), max3);
  76.  
  77. 				} else if (left[ql] == l && right[qr] != r) {
  78. 					long max1 = query(tree, ql, qr, 0, pre_tree.length - 1, 0);
  79. 					long max2 = r - left[qr + 1] + 1;
  80. 					ans = Math.max(max1, max2);
  81. 				} else if (left[ql] != l && right[qr] == r) {
  82. 					long max1 = query(tree, ql + 1, qr, 0, pre_tree.length - 1, 0);
  83. 					long max2 = right[ql] - l + 1;
  84. 					ans = Math.max(max1, max2);
  85. 				} else {
  86. 					ans = query(tree, ql, qr, 0, pre_tree.length - 1, 0);
  87. 				}
  88. 				w.println(ans);
  89. 			}
  90. 			n = s.nextInt();
  91. 			if (n == 0)
  92. 				break;
  93. 		}
  94. 		w.close();
  95.  
  96. 	}
  97.  
  98. 	static int binarySearch(long a[], long key) {
  99. 		int low = 0, high = a.length - 1;
  100. 		while (low <= high) {
  101. 			int mid = (low + high) / 2;
  102. 			if (a[mid] == key) {
  103. 				high = mid;
  104. 				break;
  105. 			} else if (a[mid] > key)
  106. 				high = mid - 1;
  107. 			else
  108. 				low = mid + 1;
  109. 		}
  110. 		return high;
  111.  
  112. 	}
  113.  
  114. 	static void make_tree(long[] a, long[] tree, int low, int high, int pos) {
  115.  
  116. 		if (low == high) {
  117. 			tree[pos] = a[low];
  118. 			return;
  119. 		}
  120. 		int mid = (low + high) >> 1;
  121. 		make_tree(a, tree, low, mid, 2 * pos + 1);
  122. 		make_tree(a, tree, mid + 1, high, 2 * pos + 2);
  123. 		if (tree[2 * pos + 1] > tree[2 * pos + 2])
  124. 			tree[pos] = tree[2 * pos + 1];
  125. 		else
  126. 			tree[pos] = tree[2 * pos + 2];
  127. 	}
  128.  
  129. 	static long query(long[] tree, long qlow, long qhigh, long low, long high, long pos) {
  130. 		if (qlow <= low && qhigh >= high)
  131. 			return tree[(int) pos];
  132. 		if (qlow > high || qhigh < low) {
  133. 			return (Integer.MIN_VALUE);
  134. 		}
  135. 		long mid = (low + high) >> 1;
  136. 		long q1 = query(tree, qlow, qhigh, low, mid, 2 * pos + 1);
  137. 		long q2 = query(tree, qlow, qhigh, mid + 1, high, 2 * pos + 2);
  138. 		return Math.max(q1, q2);
  139.  
  140. 	}
  141.  
  142. }
  143.  
  144. class InputReader {
  145.  
  146. 	private final InputStream st;
  147. 	private final byte[] buf = new byte[8192];
  148. 	private int cc, sc;
  149. 	private SpaceCharFilter f;
  150.  
  151. 	public InputReader(InputStream st) {
  152. 		this.st = st;
  153. 	}
  154.  
  155. 	public int t() {
  156. 		if (sc == -1)
  157. 			throw new InputMismatchException();
  158. 		if (cc >= sc) {
  159. 			cc = 0;
  160. 			try {
  161. 				sc = st.read(buf);
  162. 			} catch (IOException e) {
  163. 				throw new InputMismatchException();
  164. 			}
  165. 			if (sc <= 0)
  166. 				return -1;
  167. 		}
  168. 		return buf[cc++];
  169. 	}
  170.  
  171. 	public int nextInt() {
  172. 		int c = t();
  173. 		while (isSpaceChar(c)) {
  174. 			c = t();
  175. 		}
  176. 		int sgn = 1;
  177. 		if (c == '-') {
  178. 			sgn = -1;
  179. 			c = t();
  180. 		}
  181. 		int res = 0;
  182. 		do {
  183. 			res *= 10;
  184. 			res += c - '0';
  185. 			c = t();
  186. 		} while (!isSpaceChar(c));
  187. 		return res * sgn;
  188. 	}
  189.  
  190. 	public long nextLong() {
  191. 		int c = t();
  192. 		while (isSpaceChar(c)) {
  193. 			c = t();
  194. 		}
  195. 		int sgn = 1;
  196. 		if (c == '-') {
  197. 			sgn = -1;
  198. 			c = t();
  199. 		}
  200. 		long res = 0;
  201. 		do {
  202. 			res *= 10;
  203. 			res += c - '0';
  204. 			c = t();
  205. 		} while (!isSpaceChar(c));
  206. 		return res * sgn;
  207. 	}
  208.  
  209. 	public int[] nextIntArray(int n) {
  210. 		int a[] = new int[n];
  211. 		for (int i = 0; i < n; i++) {
  212. 			a[i] = nextInt();
  213. 		}
  214. 		return a;
  215. 	}
  216.  
  217. 	public String readString() {
  218. 		int c = t();
  219. 		while (isSpaceChar(c)) {
  220. 			c = t();
  221. 		}
  222. 		StringBuilder res = new StringBuilder();
  223. 		do {
  224. 			res.appendCodePoint(c);
  225. 			c = t();
  226. 		} while (!isSpaceChar(c));
  227. 		return res.toString();
  228. 	}
  229.  
  230. 	public String nextLine() {
  231. 		int c = t();
  232. 		while (isSpaceChar(c))
  233. 			c = t();
  234. 		StringBuilder res = new StringBuilder();
  235. 		do {
  236. 			res.appendCodePoint(c);
  237. 			c = t();
  238. 		} while (!isEndOfLine(c));
  239. 		return res.toString();
  240. 	}
  241.  
  242. 	public boolean isSpaceChar(int c) {
  243. 		if (f != null)
  244. 			return f.isSpaceChar(c);
  245. 		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  246. 	}
  247.  
  248. 	private boolean isEndOfLine(int c) {
  249. 		return c == '\n' || c == '\r' || c == -1;
  250. 	}
  251.  
  252. 	public interface SpaceCharFilter {
  253. 		public boolean isSpaceChar(int ch);
  254. 	}
  255. }
Runtime error #stdin #stdout #stderr 0.04s 4386816KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at InputReader.t(Main.java:157)
	at InputReader.nextInt(Main.java:174)
	at FREQUENT.main(Main.java:12)
https://ideone.com/KBi3mM
problem FREQUENT, based on SPOJ submission 19633346 (JAVA), 2017-06-18 08:47:30
language:
Java (HotSpot 12)
created:
7 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!