제출 #1346229

#제출 시각아이디문제언어결과실행 시간메모리
1346229MuhammadSaramNLO (COCI18_nlo)C++20
33 / 110
201 ms131072 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;
	set<int> t[n+1];
	map<int,vector<int>> ad[n+1], rm[n+1];
	for (int i=1;i<=n;i++)
		t[i].insert(1), t[i].insert(m), ad[i][1].push_back(0), rm[i][m].push_back(0);
	int k;
	cin>>k;
	for (int d=1;d<=k;d++)
	{
		int x,y;
		ll r;
		cin>>x>>y>>r;
		for (int i=x-r;i<=x+r;i++)
		{
			int z=sqrtl(r*r-1ll*(x-i)*(x-i));
			int l=y-z, r=y+z;
			t[i].insert(l), t[i].insert(r);
			ad[i][l].push_back(d), rm[i][r].push_back(d);
		}
	}
	ll ans=0;
	for (int i=1;i<=n;i++)
	{
		multiset<int> se;
		int ls=1;
		while (t[i].size())
		{
			int x=*t[i].begin();t[i].erase(x);
			if (x>1)
				ans+=1ll*(x-ls-1)*(k-*se.rbegin()), ls=x;
			for (int y:ad[i][x])
				se.insert(y);
			ans+=(k-*se.rbegin());
			for (int y:rm[i][x])
				se.erase(se.find(y));
		}
	}
	cout<<ans<<endl;

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