#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define MAXN 1013
#define int long long
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int R, C, N;
pair<pll, ll> arr[MAXN];
vpl event;
set<ll> ok;
ll ans;
ll getsqrt(ll x)
{
ll res = sqrt(x);
while(res * res < x) res++;
while(res * res > x) res--;
return res;
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cout << fixed << setprecision(12);
cerr << fixed << setprecision(4);
cin >> R >> C >> N;
FOR(i, 1, N + 1)
{
ll a, b, r; cin >> a >> b >> r; a--; b--;
arr[i] = {{a, b}, r};
// FOR(j, a - r, a + r + 1)
// {
// ll d = r * r - (a - j) * (a - j);
// d = getsqrt(d);
// event[j].PB({b - d, i});
// event[j].PB({b + d + 1, -i});
// }
}
FOR(i, 0, R)
{
FOR(j, 1, N + 1)
{
ll a = arr[j].fi.fi, b = arr[j].fi.se, r = arr[j].se;
if (i < a - r || i > a + r) continue;
ll d = r * r - (a - i) * (a - i);
d = getsqrt(d);
event.PB({b - d, j});
event.PB({b + d + 1, -j});
}
sort(ALL(event));
FOR(j, 0, SZ(event))
{
auto p = event[j];
if (!ok.empty())
{
ans += (*ok.rbegin()) * (p.fi - event[j - 1].fi);
}
if (p.se < 0)
{
// cerr << "j = " << j << endl;
// cerr << "ERASE " << -p.se << endl;
ok.erase(-p.se);
}
else
{
// cerr << "INSERT " << p.se << endl;
ok.insert(p.se);
}
}
event.clear();
}
//find sum(latest day)
//the # of poitns that are inside here but inside NONE OF THE FUTURE ONES
ans = 1ll * R * C * N - ans;
cout << ans << '\n';
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
13 ms |
376 KB |
Output is correct |
| 3 |
Correct |
8 ms |
504 KB |
Output is correct |
| 4 |
Correct |
49 ms |
504 KB |
Output is correct |
| 5 |
Correct |
34 ms |
376 KB |
Output is correct |
| 6 |
Correct |
266 ms |
404 KB |
Output is correct |
| 7 |
Correct |
101 ms |
376 KB |
Output is correct |
| 8 |
Correct |
509 ms |
376 KB |
Output is correct |
| 9 |
Correct |
180 ms |
376 KB |
Output is correct |
| 10 |
Correct |
672 ms |
428 KB |
Output is correct |
