| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 776966 |
2023-07-08T12:36:50 Z |
blacktulip |
NLO (COCI18_nlo) |
C++17 |
|
201 ms |
15352 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
#define fi first
#define se second
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000;
const lo li = 100005;
const lo mod = 1000000007;
int n,m,a[li],k,flag,t,x[li],y[li],r[li];
int cev;
string s;
vector<int> v;
set<pair<int,int>> st[li];
int32_t main(void){
scanf("%lld %lld",&n,&m);
scanf("%lld",&k);
for(int i=1;i<=k;i++){
scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
}
int add=n*m;
cev=0;
for(int i=k;i>=1;i--){
int yy=x[i];
while(yy>=1){
int at=r[i]*r[i]-((yy-x[i])*(yy-x[i]));
if(at<0)break;
int kat=sqrt(at);
int l=y[i]-kat;
int r=y[i]+kat;
if(st[yy].empty()){
add-=r-l+1;
//~ cout<<yy<<" () AA "<<l<<" AA "<<r<<endl;
st[yy].insert({l,r});
yy--;
continue;
//~ cout<<yy<<" DEBUGDEBUG \n";
}
else{
auto it=st[yy].begin();
int mn=l;
int mx=r;
int say=0;
while(it!=st[yy].end()){
if((*it).fi>r)break;
if((*it).se<l){it++;continue;}
mn=min(mn,(*it).fi);
auto it1=it;
it1++;
say+=min(r,(*it).se)-max(l,(*it).fi)+1;
mx=max(mx,(*it).se);
st[yy].erase(it);
it=it1;
}
add-=r-l+1-say;
st[yy].insert({mn,mx});
}
//~ cout<<add<<" ()() "<<yy<<" ()() "<<rr<<endl;
yy--;
//~ rr--;
}
//~ cout<<add<<" tmp_add \n";
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
yy=x[i]+1;
while(yy<=n){
int at=r[i]*r[i]-((yy-x[i])*(yy-x[i]));
if(at<0)break;
int kat=sqrt(at);
int l=y[i]-kat;
int r=y[i]+kat;
if(st[yy].empty()){
add-=r-l+1;
st[yy].insert({l,r});
yy++;
continue;
}
else{
auto it=st[yy].begin();
int mn=l;
int mx=r;
int say=0;
while(it!=st[yy].end()){
if((*it).fi>r)break;
if((*it).se<l){it++;continue;}
mn=min(mn,(*it).fi);
auto it1=it;
it1++;
say+=min(r,(*it).se)-max(l,(*it).fi)+1;
mx=max(mx,(*it).se);
st[yy].erase(it);
it=it1;
}
add-=r-l+1-say;
st[yy].insert({mn,mx});
}
yy++;
//~ rr--;
}
cev+=add;
//~ cout<<add<<endl;
}
printf("%lld\n",cev);
return 0;
}
Compilation message
nlo.cpp: In function 'int32_t main()':
nlo.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
28 | scanf("%lld %lld",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
nlo.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | scanf("%lld",&k);
| ~~~~~^~~~~~~~~~~
nlo.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5004 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5648 KB |
Output is correct |
| 4 |
Correct |
13 ms |
5460 KB |
Output is correct |
| 5 |
Correct |
20 ms |
7820 KB |
Output is correct |
| 6 |
Correct |
80 ms |
8068 KB |
Output is correct |
| 7 |
Correct |
45 ms |
11468 KB |
Output is correct |
| 8 |
Correct |
147 ms |
11368 KB |
Output is correct |
| 9 |
Correct |
72 ms |
15352 KB |
Output is correct |
| 10 |
Correct |
201 ms |
12044 KB |
Output is correct |
