提出 #71313057

---

ソースコード 拡げる

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int H = 2000;
        int W = 2000;

        int[][] diff = new int[H + 2][W + 2];
        int[][] clouds = new int[N][4];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            clouds[i][0] = u;
            clouds[i][1] = d;
            clouds[i][2] = l;
            clouds[i][3] = r;

            diff[u][l]++;
            diff[u][r + 1]--;
            diff[d + 1][l]--;
            diff[d + 1][r + 1]++;
        }

        int[][] ones = new int[H + 2][W + 2];
        int currentEmptyCount = 0;

        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
                
                if (diff[i][j] == 0) {
                    currentEmptyCount++;
                } else if (diff[i][j] == 1) {
                    ones[i][j] = 1;
                }
            }
        }

        int[][] P = new int[H + 2][W + 2];
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                P[i][j] = ones[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
            }
        }

        for (int i = 0; i < N; i++) {
            int u = clouds[i][0];
            int d = clouds[i][1];
            int l = clouds[i][2];
            int r = clouds[i][3];

            int recoveredCells = P[d][r] - P[u - 1][r] - P[d][l - 1] + P[u - 1][l - 1];

            out.println(currentEmptyCount + recoveredCells);
        }

        out.flush();
    }
}

提出情報

ジャッジ結果