Submission #61696

---

Source Code Expand

import java.util.Arrays;
import java.util.Scanner;

public class Main{

	int MAX = 1<<12, N = 1<<11;
	int[][] dat;
	
	//更新したい範囲[a, b), 現在の範囲[L, R)
	void query(int a, int b, int k, int L, int R, int X){
//		System.out.println(a+" "+b+" "+L+" "+R);
		if(R <= a || b <= L)return;
		if(a <= L && R <= b){
//			System.out.println("PLUS/ "+L+" "+R);
			dat[X][k]++;
			return;
		}
		query(a, b, k*2+1, L, (L+R)/2, X);
		query(a, b, k*2+2, (L+R)/2, R, X);
	}
	
	int get(int p, int X){
		p+=N-1;
		int res = dat[X][p];
		while(p>0){
			p = (p-1)/2;
			res+=dat[X][p];
		}
		res+=dat[X][0];
		return res;
	}
	
	void run() {
		Scanner sc = new Scanner();
		dat = new int[N][MAX-1];
//		query(0, 3, 0, 0, 1024, 0);
//		query(2, 4, 0, 0, 1024, 0);
//		for(int i=0;i<5;i++)System.out.println(get(i, 0));
		int F = 1000;
		int n = sc.nextInt();
		int x1 = 1000000, x2 = -100000, y1 = 1000000, y2 = -1000000;
		while(n--!=0){
			int type = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt(), L = sc.nextInt();
			x1 = Math.min(x1, x-L+1+F);
			x2 = Math.max(x2, x+L-1+F);
			y1 = Math.min(y1, y-L+1+F);
			y2 = Math.max(y2, y+L-1+F);
			if(type==1){
				int max = y+L, min = y;
				for(int X=x-L+1;X<=x+L-1;X++){
					query(min+F, max+F, 0, 0, N, X+F);
					if(X < x)min--;
					if(x <= X)max--;
				}
			}
		}
		int res = 0;
		for(int x=x1;x<=x2;x++)for(int y=y1;y<=y2;y++)res=Math.max(res, get(y, x));
		System.out.println(res);
	}

	void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}

	class Scanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		long nextLong() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-') return -nextLong();
				long res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}
		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
		String nextLine(){
			try{
				StringBuilder res =new StringBuilder("");
				int c = System.in.read();
				while (c=='\r' || c=='\n')
					c = System.in.read();
				do {
					res.append((char) c);
					c = System.in.read();
				} while (c!='\r' && c!='\n');
				return res.toString();
			}catch (Exception e) {
				return null;
			}
		}
	}
	
	public static void main(String... args) {
		new Main().run();
	}
}

Submission Info

Judge Result