fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5. import java.util.Arrays;
  6. import java.util.Comparator;
  7.  
  8.  
  9. class ASHIGIFT {
  10. static long dispop[][],X;
  11. 	public static void main(String[] args) throws IOException {
  12. 		// TODO Auto-generated method stub
  13. Reader r=new Reader();
  14. int t=r.nextInt();
  15. StringBuilder sb=new StringBuilder();
  16. PrintWriter pr=new PrintWriter(System.out);
  17. while(t-->0){
  18. 	X=r.nextInt();
  19. 	int B=r.nextInt();
  20. 	 dispop=new long[B+10000][3];
  21. 	int i=0;
  22. 	long limit=0;
  23. 	for(;i<B;i++){
  24. 		dispop[i][0]=r.nextLong();
  25. 		dispop[i][1]=r.nextLong();
  26. 		limit+=dispop[i][1];
  27. 		dispop[i][2]=-1;
  28. 	}
  29. 	int C=r.nextInt();
  30. 	for(int j=0;j<C;j++,i++){
  31. 		dispop[i][0]=r.nextLong();
  32. 		dispop[i][2]=r.nextLong();
  33. 		dispop[i][1]=r.nextLong();
  34. 	}
  35. 	if(C==0){sb.append((limit+1)+"\n");continue;}
  36.  
  37. Arrays.sort(dispop, 0, B+C, new Comparator<long []>() {
  38.  
  39. 	@Override
  40. 	public int compare(long[] o1, long[] o2) {
  41. 		// TODO Auto-generated method stub
  42. 		if(o1[0]==o2[0])return Integer.valueOf((int) (o2[2]-o1[2]));
  43. 		return Integer.valueOf((int) (o1[0]-o2[0]));
  44. 	}
  45. });
  46.  
  47. 	/*for( i=0;i<B+C;i++){
  48. 		System.out.println(dispop[i][0]+" "+dispop[i][1]+" "+dispop[i][2]+"\n");
  49. 	}
  50. 	*/
  51. long ans=binarySearch(limit+1);
  52. sb.append(ans+"\n");
  53. }
  54. 	pr.write(sb.toString());
  55. 	pr.flush();
  56. 	pr.close();}
  57. 	private static long binarySearch(long X){
  58. 		long low=1,high=X,mid=(low+((high-low)>>1));
  59. 		while(low<high){
  60. 			mid=(low+((high-low)>>1));
  61. 			//System.out.println(mid);
  62. 			if(findmin(mid,X-1)){
  63. 				high=mid;
  64. 				//System.out.println("True\n");
  65. 			}
  66. 			else {
  67. 				low=mid+1;
  68. 			//System.out.println("False\n");
  69. 			}
  70. 		}
  71. 		mid=(low+((high-low)>>1));
  72. 		return mid;
  73. 	}
  74. 	private static boolean findmin(long p,long m){
  75. 		for(int i=0;i<dispop.length;i++){
  76. 			if(dispop[i][0]==dispop[i][1] && dispop[i][1]==dispop[i][2] && dispop[i][2]==0)break;
  77. 			if(p>=dispop[i][2] && dispop[i][2]!=-1){
  78. 				p+=dispop[i][1];
  79. 			}
  80. 			else if(dispop[i][2]==-1){
  81. 				p-=dispop[i][1];
  82. 				m-=dispop[i][1];
  83. 				if(p<=0)return false;
  84. 			}
  85. 			else if(m>=p)return false;
  86. 		//	System.out.println(p+" "+m);
  87. 		}
  88.  
  89. 		return true;
  90. 	}
  91. static class Reader {
  92. 	final private int BUFFER_SIZE = 1 << 16;
  93. 	private DataInputStream din;
  94. 	private byte[] buffer;
  95. 	private int bufferPointer, bytesRead;
  96.  
  97. 	public Reader() {
  98. 		din = new DataInputStream(System.in);
  99. 		buffer = new byte[BUFFER_SIZE];
  100. 		bufferPointer = bytesRead = 0;
  101. 	}
  102.  
  103. 	public Reader(String file_name) throws IOException {
  104. 		din = new DataInputStream(new FileInputStream(file_name));
  105. 		buffer = new byte[BUFFER_SIZE];
  106. 		bufferPointer = bytesRead = 0;
  107. 	}
  108.  
  109. 	public String readLine() throws IOException {
  110. 		byte[] buf = new byte[64];
  111. 		int cnt = 0, c;
  112. 		while ((c = read()) != -1) {
  113. 			if (c == '\n')
  114. 				break;
  115. 			buf[cnt++] = (byte) c;
  116. 		}
  117. 		return new String(buf, 0, cnt);
  118. 	}
  119.  
  120. 	public int nextInt() throws IOException {
  121. 		int ret = 0;
  122. 		byte c = read();
  123. 		while (c <= ' ')
  124. 			c = read();
  125. 		boolean neg = (c == '-');
  126. 		if (neg)
  127. 			c = read();
  128. 		do {
  129. 			ret = ret * 10 + c - '0';
  130. 		} while ((c = read()) >= '0' && c <= '9');
  131. 		if (neg)
  132. 			return -ret;
  133. 		return ret;
  134. 	}
  135.  
  136. 	public long nextLong() throws IOException {
  137. 		long ret = 0;
  138. 		byte c = read();
  139. 		while (c <= ' ')
  140. 			c = read();
  141. 		boolean neg = (c == '-');
  142. 		if (neg)
  143. 			c = read();
  144. 		do {
  145. 			ret = ret * 10 + c - '0';
  146. 		} while ((c = read()) >= '0' && c <= '9');
  147. 		if (neg)
  148. 			return -ret;
  149. 		return ret;
  150. 	}
  151.  
  152. 	public double nextDouble() throws IOException {
  153. 		double ret = 0, div = 1;
  154. 		byte c = read();
  155. 		while (c <= ' ')
  156. 			c = read();
  157. 		boolean neg = (c == '-');
  158. 		if (neg)
  159. 			c = read();
  160. 		do {
  161. 			ret = ret * 10 + c - '0';
  162. 		} while ((c = read()) >= '0' && c <= '9');
  163. 		if (c == '.')
  164. 			while ((c = read()) >= '0' && c <= '9')
  165. 				ret += (c - '0') / (div *= 10);
  166. 		if (neg)
  167. 			return -ret;
  168. 		return ret;
  169. 	}
  170.  
  171. 	private void fillBuffer() throws IOException {
  172. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  173. 		if (bytesRead == -1)
  174. 			buffer[0] = -1;
  175. 	}
  176.  
  177. 	private byte read() throws IOException {
  178. 		if (bufferPointer == bytesRead)
  179. 			fillBuffer();
  180. 		return buffer[bufferPointer++];
  181. 	}
  182.  
  183. 	public void close() throws IOException {
  184. 		if (din == null)
  185. 			return;
  186. 		din.close();
  187. 	}
  188. }
  189. }
  190. /*
  191. 1
  192. 10
  193. 6 1 3 2 4 3 1 5 3 6 3 8 7
  194. 3 1 2 3 4 5 6 7 8 9
  195. */
  196. /*
  197. 1
  198. 10
  199. 4
  200. 1 2 3 2 5 2 7 2 
  201. 3
  202. 2 1 1
  203. 4 1 1
  204. 6 1 1
  205. */
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
2
10
6 1 3 2 4 3 1 5 3 6 3 8 7
3 1 2 3 4 5 6 7 8 9
10
4
1 2 3 2 5 2 7 2 
3
2 1 1
4 1 1
6 1 1
stdout
copy 
13
6
https://ideone.com/cZDgSY
language:
Java (12.0.1)
created:
9 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!