B08 - Counting Points

atcoder.jp

点の座標を二次元配列にプロットしてから、二次元累積和を計算。

x座標用のループ変数はx、y座標用のループ変数はyと名前付けしたら、混乱が緩和された気がする。

const int H = 1500 + 1;
const int W = 1500 + 1;
var N = int.Parse(Console.ReadLine()!);
var XY = new int[H, W];
for (var i = 0; i < N; i++)
{
    var input = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
    var X = input[0];
    var Y = input[1];
    XY[Y, X]++;
}

// 横方向の累積和を計算
var Z = new int[H, W];
for (var y = 1; y < H; y++)
{
    for (var x = 1; x < W; x++)
    {
        Z[y, x] = Z[y, x - 1] + XY[y, x];
    }
}

// 縦方向の累積和を計算
for (var x = 1; x < W; x++)
{
    for (var y = 1; y < H; y++)
    {
        Z[y, x] = Z[y - 1, x] + Z[y, x];
    }
}

// 問題を読み込む
var Q = int.Parse(Console.ReadLine()!);
var a = new int[Q];
var b = new int[Q];
var c = new int[Q];
var d = new int[Q];
for (var i = 0; i < Q; i++)
{
    var input = Console.ReadLine()!.Split(' ').Select(x => int.Parse(x)).ToList();
    a[i] = input[0];
    b[i] = input[1];
    c[i] = input[2];
    d[i] = input[3];
}

// 解答する
for (var i = 0; i < Q; i++)
{
    var answer = Z[d[i], c[i]]
        + Z[b[i] - 1, a[i] - 1]
        - Z[b[i] - 1, c[i]]
        - Z[d[i], a[i] - 1];
    Console.WriteLine(answer);
}