Nlo
레이팅 미적용의견: 0
3 \(s / 64\) \(MB / 110\) points
The locals of the village Žabnik have been struggling for many years with unidentified flying objects
(UFOs) that create circles in grain fields. The damage is particularly noticeable during summer hay
mowing.
Let us imagine a rectangular grain field of \(N\) rows and \(M\) colum\(ns - th\)e upper left field is designated
by coordinates (1, 1), while the lower right field is designated by coordinates ( N, \(M\) ). In each field
there is a certain amount of grass. Initially, amount of grass in all the fields is equal to 1. In \(K\) days
UFOs of circular shape land on the field and make circles in it. On the \(i\) ^{th} morning, the UFO of radius
\(R\) {i} with the center in the field designated by the coordinates ( \(X\) { }, \(Y\) ) lands on the field and "mows" all}_{
the grass growing on covered fields. In other words, the amount of grass in the field designated by
coordinates (x, y) is reduced to 0 if it holds ( \(X\) {i} - \(x\) ) ^{2} + ( \(Y\) ≤ \(R\) } - \(y\) ) ^{2{i}{ }
{2}{ }. Each new day, with the increase of
the grass, the amount of grass in all the fields increases by 1.
On \(K\) ^{th} day in the evening, the locals will mow all the grass of the grain field that will be stored for
feeding cattle. How much is the total amount of grass they will store?
In the sample tests worth 20% of the total points it will hold \(N\) , \(M\) ≤ 1 000.
The first line contains positive integers \(N\) and \(M\) (1 ≤ \(N\) , \(M\) ≤ 100 000), dimensions of the grain field.
The second line contains positive integer \(K\) (1 ≤ \(K \le 100\)), the number of the days in which
unidentified flying objects land to the grain field before mowing.
In the i ^{th} of the following \(K\) lines there are three positive integers \(X\) {i} (1 < \(X\) < \(N\) ), \(Y\) {i} (1 < \(Y\) } < \(M\) ), and \(R\) _{i
(1 ≤ \(R\) {i} ≤min( \(X\) - 1, \(Y\) {i} - 1, \(N\) - \(X\) { }, \(M\) - \(Y\) UFO lands}_{ })) which represent the central field on which the \(i\) ^{th
and the radius the \(i\) {th}{ } UFO.
Print the total amount of grass that the locals will store after mowing.
6 6
3
4 4 2
3 3 2
2 4 1
100 100
2
50 50 49
30 30 29
33333 44444
1
11111 22222 9999output
output
68
9534
1167355751
3 s / 64 MB / 110 pointsExplanation of the first test sample:
The following matrix shows amount of grass in the grain field at the end of the first day:
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
1
1
1
1
0
1
1
The following matrix shows amount of grass in the grain field at the end of the second day:
2
2
0
2
2
2
2
0
0
0
2
2
0
0
0
0
0
2
2
0
0
0
1
1
2
2
0
1
1
2
2
2
2
1
2
2
The following matrix shows amount of grass in the grain field at the end of the third day:
3
3
1
0
3
3
3
1
0
0
0
3
1
1
1
0
1
3
3
1
1
1
2
2
3
3
1
2
2
3
3
3
3
2
3
3
The total amount of grass in the grain field at the end of the third day is equal to 68.
평가 및 의견
Nlo
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Nlo