#P3228. [Sdoi2008]棋盘控制

    ID: 2414 传统题 1000ms 512MiB 尝试: 91 已通过: 27 难度: 9 上传者: 标签>难度分类省选/NOI-模拟与实现技巧坐标变换计算几何扫描线排序与序列处理离散化数据结构普通线段树构造与建模奇偶性分析补集转化前后缀最值绝对值分段线性化线性代数与代数等差数列求和半开区间统一CF2600

[Sdoi2008]棋盘控制

[SDOI2008] 棋盘控制

题目描述

给定一个 NN 行 MM 列的棋盘,上面有 KK 个棋子。同一格可以有多个棋子。

位于 (X,Y)(X,Y)、控制范围为 RR 的棋子控制棋盘内所有满足 ∣x−X∣+∣y−Y∣≤R|x-X|+|y-Y|\le R 的格子 (x,y)(x,y)。求至少被一个棋子控制的格子总数。

输入格式

第一行包含三个正整数 N,M,KN,M,K。接下来 KK 行,每行三个正整数 X,Y,RX,Y,R,表示一个棋子所在的行、列及其控制范围,其中 1≤X≤N1\le X\le N,1≤Y≤M1\le Y\le M。

输出格式

输出一行一个整数,表示被控制的格子总数。

数据范围

1≤N,M≤1081\le N,M\le 10^8,1≤K≤1051\le K\le 10^5。

样例

4 4 3
1 1 1
3 1 1
3 3 1
10