fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5. 	static class Reader {
  6. 		final private int BUFFER_SIZE = 1 << 16;
  7. 		private DataInputStream din;
  8. 		private byte[] buffer;
  9. 		private int bufferPointer, bytesRead;
  10.  
  11. 		public Reader() {
  12. 			din = new DataInputStream(System.in);
  13. 			buffer = new byte[BUFFER_SIZE];
  14. 			bufferPointer = bytesRead = 0;
  15. 		}
  16.  
  17. 		public Reader(String file_name) throws IOException {
  18. 			din = new DataInputStream(new FileInputStream(file_name));
  19. 			buffer = new byte[BUFFER_SIZE];
  20. 			bufferPointer = bytesRead = 0;
  21. 		}
  22.  
  23. 		public String nextLine() throws IOException {
  24. 			byte[] buf = new byte[64]; // line length
  25. 			int cnt = 0, c;
  26. 			while ((c = read()) != -1) {
  27. 				if (c == '\n')
  28. 					break;
  29. 				buf[cnt++] = (byte) c;
  30. 			}
  31. 			return new String(buf, 0, cnt);
  32. 		}
  33.  
  34. 		public String next() throws IOException {
  35. 			byte[] buf = new byte[64]; // line length
  36. 			int cnt = 0, c;
  37. 			while ((c = read()) != -1) {
  38. 				if (c == ' ')
  39. 					break;
  40. 				buf[cnt++] = (byte) c;
  41. 			}
  42. 			return new String(buf, 0, cnt);
  43. 		}
  44.  
  45. 		public int nextInt() throws IOException {
  46. 			int ret = 0;
  47. 			byte c = read();
  48. 			while (c <= ' ')
  49. 				c = read();
  50. 			boolean neg = (c == '-');
  51. 			if (neg)
  52. 				c = read();
  53. 			do {
  54. 				ret = ret * 10 + c - '0';
  55. 			} while ((c = read()) >= '0' && c <= '9');
  56.  
  57. 			if (neg)
  58. 				return -ret;
  59. 			return ret;
  60. 		}
  61.  
  62. 		public long nextLong() throws IOException {
  63. 			long ret = 0;
  64. 			byte c = read();
  65. 			while (c <= ' ')
  66. 				c = read();
  67. 			boolean neg = (c == '-');
  68. 			if (neg)
  69. 				c = read();
  70. 			do {
  71. 				ret = ret * 10 + c - '0';
  72. 			} while ((c = read()) >= '0' && c <= '9');
  73. 			if (neg)
  74. 				return -ret;
  75. 			return ret;
  76. 		}
  77.  
  78. 		public double nextDouble() throws IOException {
  79. 			double ret = 0, div = 1;
  80. 			byte c = read();
  81. 			while (c <= ' ')
  82. 				c = read();
  83. 			boolean neg = (c == '-');
  84. 			if (neg)
  85. 				c = read();
  86.  
  87. 			do {
  88. 				ret = ret * 10 + c - '0';
  89. 			} while ((c = read()) >= '0' && c <= '9');
  90.  
  91. 			if (c == '.') {
  92. 				while ((c = read()) >= '0' && c <= '9') {
  93. 					ret += (c - '0') / (div *= 10);
  94. 				}
  95. 			}
  96.  
  97. 			if (neg)
  98. 				return -ret;
  99. 			return ret;
  100. 		}
  101.  
  102. 		private void fillBuffer() throws IOException {
  103. 			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  104. 			if (bytesRead == -1)
  105. 				buffer[0] = -1;
  106. 		}
  107.  
  108. 		private byte read() throws IOException {
  109. 			if (bufferPointer == bytesRead)
  110. 				fillBuffer();
  111. 			return buffer[bufferPointer++];
  112. 		}
  113.  
  114. 		public void close() throws IOException {
  115. 			if (din == null)
  116. 				return;
  117. 			din.close();
  118. 		}
  119. 	}
  120.  
  121. 	static Reader s = new Reader();
  122. 	static PrintWriter out = new PrintWriter(System.out);
  123.  
  124. 	public static void main(String[] args) throws IOException {
  125. 		int t = s.nextInt();
  126. 		StringBuffer sb = new StringBuffer();
  127. 		long sum = 0, a, b, c, d, med, z; int n;
  128. 		while (t > 0) {
  129. 			t--;
  130. 			PriorityQueue<Long> max = new PriorityQueue<>(new Compare1());
  131. 			PriorityQueue<Long> min = new PriorityQueue<>();
  132. 			a = s.nextLong();
  133. 			b = s.nextLong();
  134. 			c = s.nextLong();
  135. 			n = s.nextInt();
  136. 			d = b;
  137. 			sum = 1;
  138. 			max.add(1l);
  139. 			b += d;
  140. 			for(int i = 2; i <= n; i++) {
  141. 				int mxs = max.size(), mis = min.size();
  142. 				long mxp = max.peek(); 
  143. 				long mip = -1l;
  144. 				if(mis != 0) mip = min.peek();
  145. 				med = mxp;
  146. 				z = ((a * med) + b + c) % 1000000007;
  147. 				b += d;
  148. 				//if(i == 1) z = 1;
  149. 				sum += z;
  150. 				if(mxs == mis) {
  151. 					if(mis == 0) max.add(z);
  152. 					else if(mxp <= z && mip >= z) {
  153. 						max.add(z);
  154. 					}
  155. 					else if(mip < z) {
  156. 						max.add(min.poll());
  157. 						min.add(z);
  158. 					}
  159. 					else {
  160. 						max.add(z);
  161. 					}
  162. 				}
  163. 				else {
  164. 					if(mis == 0) {
  165. 						if(mxp <= z) min.add(z);
  166. 						else {
  167. 							min.add(max.poll());
  168. 							max.add(z);
  169. 						}
  170. 					}
  171. 					else if(mxp <= z) {
  172. 						min.add(z);
  173. 					}
  174. 					else {
  175. 						min.add(max.poll());
  176. 						max.add(z);
  177. 					}
  178. 				}
  179. 			}
  180. 			max = null; min = null;
  181. 			sb.append(sum + "\n");
  182. 		}
  183. 		out.print(sb);
  184. 		out.flush();
  185. 	}
  186.  
  187. }
  188.  
  189.  
  190. class Compare1 implements Comparator<Long>{
  191.  
  192. 	@Override
  193. 	public int compare(Long p1, Long p2) {
  194. 		return (p1 - p2 > 0) ? -1 : 1;
  195. 	}
  196. }
Success #stdin #stdout 0.08s 34120KB
comments (?)
stdin
copy 
2
1 0 0 3
3 1 2 6
stdout
copy 
3
103
https://ideone.com/YAdoQl
problem WEIRDFN, based on SPOJ submission 24885539 (JAVA), 2019-11-17 12:25:40
language:
Java (HotSpot 12)
created:
4 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!