| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 702432 |
2023-02-24T05:06:50 Z |
chenyan |
NLO (COCI18_nlo) |
C++17 |
|
981 ms |
2028 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define N 200010
int ans,x[N],y[N],r[N],sq[N];
struct A{
int l,r,w;
};
vector<A>v;
vector<int>u;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,m,i,j,k;
cin>>n>>m>>k;
for(i=0;i<N;i++)sq[i]=i*i;
for(i=1;i<=k;i++) cin>>x[i]>>y[i]>>r[i];
for(j=1;j<=n;j++){
for(i=1;i<=k;i++){
int xx=r[i]*r[i]-(j-x[i])*(j-x[i]);
if(xx<0)continue;
int p=upper_bound(sq,sq+N,xx)-sq-1;
v.pb({y[i]-p,y[i]+p+1,i});
u.pb(v.back().l);
u.pb(v.back().r);
}
sort(all(u)),u.resize(unique(all(u))-u.begin());
for(auto&[l,r,w]:v){
l=lower_bound(all(u),l)-u.begin();
r=lower_bound(all(u),r)-u.begin();
}
sort(all(v),[](A u,A v){return u.l<v.l;});
priority_queue<pii>pq;
pq.push({0,1e9});
int l=1,x;
for(i=0,x=0;i<u.size();i++){
ans+=(u[i]-l)*pq.top().ff;
l=u[i];
while(x<k&&v[x].l==i)pq.push({v[x].w,v[x].r}),x++;
while(pq.top().ss<=i)pq.pop();
}
vector<int>().swap(u);
vector<A>().swap(v);
}
cout<<n*m*k-ans<<'\n';
}
Compilation message
nlo.cpp: In function 'int main()':
nlo.cpp:41:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(i=0,x=0;i<u.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1876 KB |
Output isn't correct |
| 2 |
Incorrect |
14 ms |
1872 KB |
Output isn't correct |
| 3 |
Incorrect |
10 ms |
1868 KB |
Output isn't correct |
| 4 |
Incorrect |
70 ms |
1992 KB |
Output isn't correct |
| 5 |
Incorrect |
48 ms |
1868 KB |
Output isn't correct |
| 6 |
Incorrect |
400 ms |
1912 KB |
Output isn't correct |
| 7 |
Incorrect |
141 ms |
1876 KB |
Output isn't correct |
| 8 |
Incorrect |
736 ms |
2024 KB |
Output isn't correct |
| 9 |
Incorrect |
242 ms |
1876 KB |
Output isn't correct |
| 10 |
Incorrect |
981 ms |
2028 KB |
Output isn't correct |
