| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 776759 |
2023-07-08T08:39:25 Z |
vjudge1 |
NLO (COCI18_nlo) |
C++17 |
|
193 ms |
15348 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];
//~ r[i]++;
int rr=r[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=100000000;
int mx=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++;
if(it1==st[yy].end() || (*it).se>=r){
mx=max(mx,(*it).se);
st[yy].erase(it);
break;
}
//~ cout<<(*it1).fi<<" ()() "<<(*it).se<<endl;
if(min(r,(*it1).fi)-max(l,(*it).se)>=0)add-=min(r,(*it1).fi)-max(l,(*it).se);
mx=max(mx,(*it).se);
st[yy].erase(it);
it=it1;
}
//~ cout<<mn<<" ()() "<<mx<<endl;
if(mn==100000000 && mx==0){
mn=l;
mx=r;
add-=r-l+1;
}
if(mn>l){add-=mn-l;mn=l;}
if(r>mx){add-=r-mx;mx=r;}
st[yy].insert({mn,mx});
}
//~ cout<<add<<" ()() "<<yy<<" ()() "<<rr<<endl;
yy--;
rr--;
}
//~ cout<<add<<" tmp_add \n";
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
yy=x[i]+1;
rr=r[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=100000000;
int mx=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++;
if(it1==st[yy].end() || (*it).se>=r){
mx=max(mx,(*it).se);
st[yy].erase(it);
break;
}
if(min(r,(*it1).fi)-max(l,(*it).se)>=0)add-=min(r,(*it1).fi)-max(l,(*it).se);
mx=max(mx,(*it).se);
st[yy].erase(it);
it=it1;
}
//~ cout<<mn<<" [][] "<<mx<<endl;
if(mn==100000000 && mx==0){
mn=l;
mx=r;
add-=r-l+1;
}
if(mn>l){add-=mn-l;mn=l;}
if(r>mx){add-=r-mx;mx=r;}
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 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
5008 KB |
Output isn't correct |
| 3 |
Incorrect |
4 ms |
5664 KB |
Output isn't correct |
| 4 |
Incorrect |
13 ms |
5552 KB |
Output isn't correct |
| 5 |
Incorrect |
16 ms |
7776 KB |
Output isn't correct |
| 6 |
Incorrect |
76 ms |
8080 KB |
Output isn't correct |
| 7 |
Incorrect |
38 ms |
11476 KB |
Output isn't correct |
| 8 |
Incorrect |
140 ms |
11368 KB |
Output isn't correct |
| 9 |
Incorrect |
74 ms |
15348 KB |
Output isn't correct |
| 10 |
Incorrect |
193 ms |
12044 KB |
Output isn't correct |
