| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 146816 |
2019-08-26T09:32:35 Z |
gumball |
NLO (COCI18_nlo) |
C++14 |
|
605 ms |
504 KB |
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,m,k,i,j,X[110],Y[110],R[110],d[110],has;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
cin>>k;
for(i=1;i<=k;i++)
cin>>X[i]>>Y[i]>>R[i];
for(i=1;i<=n;i++)
{
vector<pair<ll,ll> > isi;
isi.pb(mp(1,k+1));
isi.pb(mp(m+1,-(k+1)));
priority_queue<ll> pq;
for(j=1;j<=k;j++)
{
ll A=abs(X[j]-i);
if(A>R[j])continue;
ll bes=sqrt(R[j]*R[j]-A*A);
ll ki=max(1LL,Y[j]-bes);
ll ka=min(m,Y[j]+bes);
isi.pb(mp(ki,k-j+1));
isi.pb(mp(ka+1,-(k-j+1)));
}
sort(isi.begin(),isi.end());
ll sz=isi.size();
for(j=0;j<sz;j++)
{
if(isi[j].se>0)
{
d[isi[j].se]++;
pq.push(-isi[j].se);
}
else
{
d[-isi[j].se]--;
while((!pq.empty())&&(d[-pq.top()]==0))
pq.pop();
}
if((j<(sz-1))&&(isi[j].fi!=isi[j+1].fi))
has+=(isi[j+1].fi-isi[j].fi)*((-pq.top())-1);
}
}
cout<<has<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Correct |
11 ms |
376 KB |
Output is correct |
| 3 |
Correct |
11 ms |
376 KB |
Output is correct |
| 4 |
Correct |
39 ms |
504 KB |
Output is correct |
| 5 |
Correct |
34 ms |
504 KB |
Output is correct |
| 6 |
Correct |
229 ms |
392 KB |
Output is correct |
| 7 |
Correct |
108 ms |
504 KB |
Output is correct |
| 8 |
Correct |
407 ms |
504 KB |
Output is correct |
| 9 |
Correct |
207 ms |
504 KB |
Output is correct |
| 10 |
Correct |
605 ms |
504 KB |
Output is correct |
