Submission #163233

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
163233	2019-11-11T23:27:26 Z	qkxwsm	NLO (COCI18_nlo)	C++14	110 / 110	672 ms	504 KB

nlo

#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;
}

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	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