fork(2) download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6. import java.math.*;
  7.  
  8. /* Name of the class has to be "Main" only if the class is public. */
  9. class Main
  10. {
  11. 	public static void main (String[] args) throws java.lang.Exception
  12. 	{
  13. 		new Main().run();
  14. 	}
  15.  
  16. 	int inf_res[] = {Integer.MAX_VALUE, Integer.MAX_VALUE};
  17. 	int a[], t[][];
  18.  
  19. 	StreamTokenizer st;
  20. 	PrintWriter out;
  21.  
  22. 	void run() {
  23. 		try {
  24. 			st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
  25. 			out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  26. 			int n = nextInt();
  27. 			int k = nextInt();
  28. 			a = new int[n];
  29. 			for (int i = 0; i < n; i++) {
  30. 				a[i] = nextInt();
  31. 			}
  32. 			t = new int[2][4 * n];
  33. 			build(1, 0, n - 1);
  34. 			int m = nextInt();
  35. 			for (int i = 0; i < m; i++) {
  36. 				int q = nextInt();
  37. 				if (q == 1) {
  38. 					int l = nextInt() - 1;
  39. 					int r = nextInt() - 1;
  40. 					int[] res = query(1, 0, n - 1, l, r);
  41. 					if (res[0] < Integer.MAX_VALUE && res[1] < Integer.MAX_VALUE && res[0] + res[1] <= k)
  42. 						out.println("Yes");
  43. 					else
  44. 						out.println("No");
  45. 				} else {
  46. 					int l = nextInt() - 1;
  47. 					int x = nextInt();
  48. 					update(1, 0, n - 1, l, x);
  49. 				}
  50. 			}
  51. 			out.close();
  52. 		} catch (Exception e) {
  53. 			e.printStackTrace(out);
  54. 			out.close();
  55. 			//while (true);
  56. 		}
  57. 	}
  58.  
  59. 	void combine(int s1, int s2, int res) {
  60. 		if (t[0][s1] < t[0][s2]) {
  61. 			t[0][res] = t[0][s1];
  62. 			if (t[1][s1] < t[0][s2])
  63. 				t[1][res] = t[1][s1];
  64. 			else
  65. 				t[1][res] = t[0][s2];
  66. 		} else {
  67. 			t[0][res] = t[0][s2];
  68. 			if (t[0][s1] < t[1][s2])
  69. 				t[1][res] = t[0][s1];
  70. 			else
  71. 				t[1][res] = t[1][s2];
  72. 		}
  73. 	}
  74.  
  75. 	void combine2(int[] s1, int[] s2, int[] res) {
  76. 		if (s1[0] < s2[0]) {
  77. 			res[0] = s1[0];
  78. 			if (s1[1] < s2[0])
  79. 				res[1] = s1[1];
  80. 			else
  81. 				res[1] = s2[0];
  82. 		} else {
  83. 			res[0] = s2[0];
  84. 			if (s1[0] < s2[1])
  85. 				res[1] = s1[0];
  86. 			else
  87. 				res[1] = s2[1];
  88. 		}
  89. 	}
  90.  
  91. 	void build(int v, int tl, int tr) {
  92. 		if (tl == tr) {
  93. 			t[0][v] = a[tl];
  94. 			t[1][v] = Integer.MAX_VALUE;
  95. 			return;
  96. 		}
  97. 		int tm = (tl + tr) >> 1;
  98. 		build(v << 1, tl, tm);
  99. 		build((v << 1) + 1, tm + 1, tr);
  100. 		combine(v << 1, (v << 1) + 1, v);
  101. 	}
  102.  
  103. 	void update(int v, int tl, int tr, int pos, int x) {
  104. 		if (tl == tr) {
  105. 			t[0][v] = x;
  106. 			t[1][v] = Integer.MAX_VALUE;
  107. 			return;
  108. 		}
  109. 		int tm = (tl + tr) >> 1;
  110. 		if (pos <= tm)
  111. 			update(v << 1, tl, tm, pos, x);
  112. 		else
  113. 			update((v << 1) + 1, tm + 1, tr, pos, x);
  114. 		combine(v << 1, (v << 1) + 1, v);
  115. 	}
  116.  
  117. 	int[] query(int v, int tl, int tr, int l, int r) {
  118. 		if (l > r)
  119. 			return inf_res;
  120. 		if (l == tl && r == tr) {
  121. 			int[] res = new int[2];
  122. 			res[0] = t[0][v];
  123. 			res[1] = t[1][v];
  124. 			return res;
  125. 		}
  126. 		int tm = (tl + tr) >> 1;
  127. 		int[] q1 = query(v << 1, tl, tm, l, Math.min(tm, r));
  128. 		int[] q2 = query((v << 1) + 1, tm + 1, tr,  Math.max(l, tm + 1), r);
  129. 		int[] res = new int[2];
  130. 		combine2(q1, q2, res);
  131. 		return res;
  132. 	}
  133.  
  134. 	int nextInt() throws Exception {
  135. 		st.nextToken();
  136. 		return (int) st.nval;
  137. 	}
  138.  
  139. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
6 9
1 3 1 6 6 7
8
1 1 6
1 1 2
2 4 7
1 4 5
1 5 6
2 1 7
2 3 8
1 1 6
stdout
copy 
Yes
Yes
No
No
Yes
https://ideone.com/Kjk0BQ
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

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!