Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class Test4 {
- public static class Query implements Comparable<Query>{
- int id, typ; long x;
- public Query(long x, int typ, int id) {
- this.x = x;
- this.id = id;
- this.typ = typ;
- }
- public int compareTo(Query q) {
- if(this.x == q.x) {
- return Integer.compare(this.typ, q.typ);
- }
- return Long.compare(this.x, q.x);
- }
- }
- public static void main(String[] args) throws IOException {
- int N = readInt();
- long qx[] = new long[N+1], qy[] = new long[N+1];
- for(int i =1; i<=N; i++) {
- int x = readInt(), y = readInt();
- qx[i] = x-y;
- qy[i] = x+y;
- }
- int M = readInt();
- long nx[] = new long[M+1], ny[] = new long[M+1];
- for(int i =1; i<=M; i++) {
- int x = readInt(), y = readInt();
- nx[i] = x-y;
- ny[i] = x+y;
- }
- long rangeL[] = new long[N+1], rangeR[] = new long[N+1];
- long ans[] = new long[N+1];
- for(int i =1; i<=N; i++) {
- rangeL[i] = 0;
- rangeR[i] = 4000000000L;
- }
- for(int t = 0; t<33; t++) {
- Query qu[] = new Query[2*N+M];
- Long cmp[] = new Long[2*N+M];
- int ty[] = new int[N+1], by[] = new int[N+1], n[] = new int[M+1];
- for(int i = 1; i<=N; i++) {
- long mid = ((1L*rangeL[i]+rangeR[i])/2);
- cmp[2*i-2] = qy[i]+mid;
- cmp[2*i-1] = qy[i]-mid;
- }
- for(int i = 2*N; i<2*N+M; i++) {
- cmp[i] = 1L*ny[i-2*N+1];
- }
- Arrays.sort(cmp);
- for(int i = 1; i<=N; i++) {
- long mid = ((1L*rangeL[i]+rangeR[i])/2);
- ty[i] = Arrays.binarySearch(cmp, qy[i]+mid)+2;
- by[i] = Arrays.binarySearch(cmp, qy[i]-mid)+2;
- qu[2*i-2] = new Query(qx[i]-mid, 0, i);
- qu[2*i-1] = new Query(qx[i]+mid, 2, i);
- }
- for(int i = 2*N; i<2*N+M; i++) {
- n[i-2*N+1] = Arrays.binarySearch(cmp, 1L*ny[i-2*N+1])+2;
- qu[i] = new Query(nx[i-2*N+1], 1, i-2*N+1);
- }
- Arrays.sort(qu);
- int sum[] = new int[N+1];
- BIT = new int[2*N+M+5];
- for(Query q : qu) {
- if(q.typ == 1) {
- upd(n[q.id]);
- }
- else if(q.typ == 0) {
- sum[q.id] -= query(ty[q.id]) - query(by[q.id]-1);
- }
- else {
- sum[q.id] += query(ty[q.id]) - query(by[q.id]-1);
- }
- }
- for(int i =1; i<=N; i++) {
- long mid = ((1L*rangeL[i]+rangeR[i])/2);
- if(sum[i] > 0) {
- ans[i] = mid;
- rangeR[i] = mid - 1;
- }
- else {
- rangeL[i] = mid + 1;
- }
- }
- }
- long tot = 0;
- for(int i = 1; i<=N; i++) {
- tot += ans[i];
- }
- println(tot);
- exit();
- }
- static int BIT[];
- static int query(int n) {
- int sum = 0;
- for(int i = n; i>0; i-=i&-i) {
- sum += BIT[i];
- }
- return sum;
- }
- static void upd(int n) {
- for(int i = n; i<BIT.length; i+=i&-i) {
- BIT[i]++;
- }
- }
- final private static int BUFFER_SIZE = 1 << 16;
- private static DataInputStream din = new DataInputStream(System.in);
- private static byte[] buffer = new byte[BUFFER_SIZE];
- private static int bufferPointer = 0, bytesRead = 0;
- static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
- public static String readLine() throws IOException {
- byte[] buf = new byte[64]; // line length
- int cnt = 0, c;
- while ((c = Read()) != -1) {
- if (c == '\n')
- break;
- buf[cnt++] = (byte) c;
- }
- return new String(buf, 0, cnt);
- }
- public static String read() throws IOException {
- byte[] ret = new byte[1024];
- int idx = 0;
- byte c = Read();
- while (c <= ' ') {
- c = Read();
- }
- do {
- ret[idx++] = c;
- c = Read();
- } while (c != -1 && c != ' ' && c != '\n' && c != '\r');
- return new String(ret, 0, idx);
- }
- public static int readInt() throws IOException {
- int ret = 0;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public static long readLong() throws IOException {
- long ret = 0;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (neg)
- return -ret;
- return ret;
- }
- public static double readDouble() throws IOException {
- double ret = 0, div = 1;
- byte c = Read();
- while (c <= ' ')
- c = Read();
- boolean neg = (c == '-');
- if (neg)
- c = Read();
- do {
- ret = ret * 10 + c - '0';
- } while ((c = Read()) >= '0' && c <= '9');
- if (c == '.') {
- while ((c = Read()) >= '0' && c <= '9') {
- ret += (c - '0') / (div *= 10);
- }
- }
- if (neg)
- return -ret;
- return ret;
- }
- private static void fillBuffer() throws IOException {
- bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
- if (bytesRead == -1)
- buffer[0] = -1;
- }
- private static byte Read() throws IOException {
- if (bufferPointer == bytesRead)
- fillBuffer();
- return buffer[bufferPointer++];
- }
- static void print(Object o) {
- pr.print(o);
- }
- static void println(Object o) {
- pr.println(o);
- }
- static void flush() {
- pr.flush();
- }
- static void println() {
- pr.println();
- }
- static void exit() throws IOException {
- din.close();
- pr.close();
- System.exit(0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement