5541번: 釘

https://www.acmicpc.net/problem/5541


$O(n^2+m)$

prefix sum을 이용한다.
https://www.ioi-jp.org/joi/2011/2012-ho-prob_and_sol/2012-ho-t4-review.pdf
일본어지만 그림으로 풀이를 대강 유추할 수 있을 것이다.(설명이 필요하다면 덧글로)

#include<cstdio>
int n, m, r, s[5003][5003];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y, z; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);
        s[x][y]++; s[x][y + 1]--;
        s[x + z + 1][y]--; s[x + z + 1][y + z + 2]++;
        s[x + z + 2][y + 1]++; s[x + z + 2][y + z + 2]--;
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) s[i][j] += s[i - 1][j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) s[i][j] += s[i][j - 1];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) r += (s[i][j] += s[i - 1][j - 1]) > 0;
    printf("%d", r);
    return 0;
}