Advertisement
Guest User

Untitled

a guest
Nov 18th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.21 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Test4 {
  5.  
  6. public static class Query implements Comparable<Query>{
  7. int id, typ; long x;
  8. public Query(long x, int typ, int id) {
  9. this.x = x;
  10. this.id = id;
  11. this.typ = typ;
  12. }
  13. public int compareTo(Query q) {
  14. if(this.x == q.x) {
  15. return Integer.compare(this.typ, q.typ);
  16. }
  17. return Long.compare(this.x, q.x);
  18. }
  19. }
  20.  
  21. public static void main(String[] args) throws IOException {
  22. int N = readInt();
  23. long qx[] = new long[N+1], qy[] = new long[N+1];
  24. for(int i =1; i<=N; i++) {
  25. int x = readInt(), y = readInt();
  26. qx[i] = x-y;
  27. qy[i] = x+y;
  28. }
  29. int M = readInt();
  30. long nx[] = new long[M+1], ny[] = new long[M+1];
  31. for(int i =1; i<=M; i++) {
  32. int x = readInt(), y = readInt();
  33. nx[i] = x-y;
  34. ny[i] = x+y;
  35. }
  36. long rangeL[] = new long[N+1], rangeR[] = new long[N+1];
  37. long ans[] = new long[N+1];
  38. for(int i =1; i<=N; i++) {
  39. rangeL[i] = 0;
  40. rangeR[i] = 4000000000L;
  41. }
  42. for(int t = 0; t<33; t++) {
  43. Query qu[] = new Query[2*N+M];
  44. Long cmp[] = new Long[2*N+M];
  45. int ty[] = new int[N+1], by[] = new int[N+1], n[] = new int[M+1];
  46. for(int i = 1; i<=N; i++) {
  47. long mid = ((1L*rangeL[i]+rangeR[i])/2);
  48. cmp[2*i-2] = qy[i]+mid;
  49. cmp[2*i-1] = qy[i]-mid;
  50. }
  51. for(int i = 2*N; i<2*N+M; i++) {
  52. cmp[i] = 1L*ny[i-2*N+1];
  53. }
  54. Arrays.sort(cmp);
  55. for(int i = 1; i<=N; i++) {
  56. long mid = ((1L*rangeL[i]+rangeR[i])/2);
  57. ty[i] = Arrays.binarySearch(cmp, qy[i]+mid)+2;
  58. by[i] = Arrays.binarySearch(cmp, qy[i]-mid)+2;
  59. qu[2*i-2] = new Query(qx[i]-mid, 0, i);
  60. qu[2*i-1] = new Query(qx[i]+mid, 2, i);
  61. }
  62. for(int i = 2*N; i<2*N+M; i++) {
  63. n[i-2*N+1] = Arrays.binarySearch(cmp, 1L*ny[i-2*N+1])+2;
  64. qu[i] = new Query(nx[i-2*N+1], 1, i-2*N+1);
  65. }
  66. Arrays.sort(qu);
  67. int sum[] = new int[N+1];
  68. BIT = new int[2*N+M+5];
  69. for(Query q : qu) {
  70. if(q.typ == 1) {
  71. upd(n[q.id]);
  72. }
  73. else if(q.typ == 0) {
  74. sum[q.id] -= query(ty[q.id]) - query(by[q.id]-1);
  75. }
  76. else {
  77. sum[q.id] += query(ty[q.id]) - query(by[q.id]-1);
  78. }
  79. }
  80. for(int i =1; i<=N; i++) {
  81. long mid = ((1L*rangeL[i]+rangeR[i])/2);
  82. if(sum[i] > 0) {
  83. ans[i] = mid;
  84. rangeR[i] = mid - 1;
  85. }
  86. else {
  87. rangeL[i] = mid + 1;
  88. }
  89. }
  90. }
  91. long tot = 0;
  92. for(int i = 1; i<=N; i++) {
  93. tot += ans[i];
  94. }
  95. println(tot);
  96. exit();
  97. }
  98.  
  99. static int BIT[];
  100.  
  101. static int query(int n) {
  102. int sum = 0;
  103. for(int i = n; i>0; i-=i&-i) {
  104. sum += BIT[i];
  105. }
  106. return sum;
  107. }
  108.  
  109. static void upd(int n) {
  110. for(int i = n; i<BIT.length; i+=i&-i) {
  111. BIT[i]++;
  112. }
  113. }
  114.  
  115. final private static int BUFFER_SIZE = 1 << 16;
  116. private static DataInputStream din = new DataInputStream(System.in);
  117. private static byte[] buffer = new byte[BUFFER_SIZE];
  118. private static int bufferPointer = 0, bytesRead = 0;
  119. static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
  120.  
  121. public static String readLine() throws IOException {
  122. byte[] buf = new byte[64]; // line length
  123. int cnt = 0, c;
  124. while ((c = Read()) != -1) {
  125. if (c == '\n')
  126. break;
  127. buf[cnt++] = (byte) c;
  128. }
  129. return new String(buf, 0, cnt);
  130. }
  131.  
  132. public static String read() throws IOException {
  133. byte[] ret = new byte[1024];
  134. int idx = 0;
  135. byte c = Read();
  136. while (c <= ' ') {
  137. c = Read();
  138. }
  139. do {
  140. ret[idx++] = c;
  141. c = Read();
  142. } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
  143. return new String(ret, 0, idx);
  144. }
  145.  
  146. public static int readInt() throws IOException {
  147. int ret = 0;
  148. byte c = Read();
  149. while (c <= ' ')
  150. c = Read();
  151. boolean neg = (c == '-');
  152. if (neg)
  153. c = Read();
  154. do {
  155. ret = ret * 10 + c - '0';
  156. } while ((c = Read()) >= '0' && c <= '9');
  157.  
  158. if (neg)
  159. return -ret;
  160. return ret;
  161. }
  162.  
  163. public static long readLong() throws IOException {
  164. long ret = 0;
  165. byte c = Read();
  166. while (c <= ' ')
  167. c = Read();
  168. boolean neg = (c == '-');
  169. if (neg)
  170. c = Read();
  171. do {
  172. ret = ret * 10 + c - '0';
  173. } while ((c = Read()) >= '0' && c <= '9');
  174. if (neg)
  175. return -ret;
  176. return ret;
  177. }
  178.  
  179. public static double readDouble() throws IOException {
  180. double ret = 0, div = 1;
  181. byte c = Read();
  182. while (c <= ' ')
  183. c = Read();
  184. boolean neg = (c == '-');
  185. if (neg)
  186. c = Read();
  187.  
  188. do {
  189. ret = ret * 10 + c - '0';
  190. } while ((c = Read()) >= '0' && c <= '9');
  191.  
  192. if (c == '.') {
  193. while ((c = Read()) >= '0' && c <= '9') {
  194. ret += (c - '0') / (div *= 10);
  195. }
  196. }
  197.  
  198. if (neg)
  199. return -ret;
  200. return ret;
  201. }
  202.  
  203. private static void fillBuffer() throws IOException {
  204. bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  205. if (bytesRead == -1)
  206. buffer[0] = -1;
  207. }
  208.  
  209. private static byte Read() throws IOException {
  210. if (bufferPointer == bytesRead)
  211. fillBuffer();
  212. return buffer[bufferPointer++];
  213. }
  214.  
  215. static void print(Object o) {
  216. pr.print(o);
  217. }
  218.  
  219. static void println(Object o) {
  220. pr.println(o);
  221. }
  222.  
  223. static void flush() {
  224. pr.flush();
  225. }
  226.  
  227. static void println() {
  228. pr.println();
  229. }
  230.  
  231. static void exit() throws IOException {
  232. din.close();
  233. pr.close();
  234. System.exit(0);
  235. }
  236. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement