제출 #1346241

#제출 시각아이디문제언어결과실행 시간메모리
1346241MuhammadSaramNLO (COCI18_nlo)C++20
110 / 110
1206 ms476 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);

	int n,m;
	cin>>n>>m;
	int k;
	cin>>k;
	int x[k+1], y[k+1];
	ll r[k+1];
	for (int d=1;d<=k;d++)
		cin>>x[d]>>y[d]>>r[d];
	ll ans=0;
	for (int i=1;i<=n;i++)
	{
		set<int> t;
		map<int,vector<int>> ad, rm;
		t.insert(1), t.insert(m), ad[1].push_back(0), rm[m].push_back(0);
		for (int d=1;d<=k;d++)
		{
			if (abs(i-x[d])>r[d]) continue;
			int z=sqrtl(r[d]*r[d]-1ll*(x[d]-i)*(x[d]-i));
			int l=y[d]-z, r1=y[d]+z;
			t.insert(l), t.insert(r1);
			ad[l].push_back(d), rm[r1].push_back(d);
		}
		multiset<int> se;
		int ls=1;
		while (t.size())
		{
			int x=*t.begin();t.erase(x);
			if (x>1)
				ans+=1ll*(x-ls-1)*(k-*se.rbegin()), ls=x;
			for (int y:ad[x])
				se.insert(y);
			ans+=(k-*se.rbegin());
			for (int y:rm[x])
				se.erase(se.find(y));
		}
	}
	cout<<ans<<endl;

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...