Star sky | Codeforces #427 (Div. 2)

// 思いつき方
// 明るさが最大11種類しかないことに注目

// s, x, y
// 部分和sm[s][x][y2]-sm[s][x][y1]は
// 初期の明るさsの星のうち、
// (x, y1), (x, y1+1), ... , (x, y2-1)
// にある星の数
int sm[11][101][101];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q, c;
    cin >> n >> q >> c;
    rep(i, n) {
        int x, y, s;
        cin >> x >> y >> s;
        sm[s][x][y]++;
    }
    // sm[i][x]ごとに部分和を計算する
    rep(i, c + 1)rep(x, 101)rep(y, 100)sm[i][x][y + 1] += sm[i][x][y];

    while (q--) {
        int t, X1, Y1, X2, Y2, ans = 0;
        cin >> t >> X1 >> Y1 >> X2 >> Y2;

        for (int x = X1; x <= X2; ++x) { // 矩形内のすべてのx座標について
            rep(s, c + 1) {
                // 初期の明るさがsである星は
                // t秒後には
                // (s+t) % (c+1)の明るさになる。
                int bri = (s + t) % (c + 1);
                // 明るさ * 星の数
                ans += bri * (sm[s][x][Y2] - sm[s][x][Y1 - 1]);
            }
        }
        cout << ans << endl;
    }
}