| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 776740 |
2023-07-08T08:13:22 Z |
vjudge1 |
NLO (COCI18_nlo) |
C++17 |
|
195 ms |
15408 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;
st[yy].insert({l,r});
yy--;
continue;
//~ cout<<yy<<" DEBUGDEBUG \n";
}
else{
auto it=st[yy].upper_bound({l,1000000});
int mn=0;
int mx=0;
if(it==st[yy].begin()){
if((*it).fi<=r){
mn=l;
add-=(*it).fi-l;
}
else{
mn=l;
mx=r;
add-=(r-l+1);
st[yy].insert({mn,mx});
yy--;
continue;
}
}
else{
it--;
if((*it).se<l){
it++;
if(it!=st[yy].end() && (*it).fi<=r){
mn=l;
add-=(*it).fi-l;
}
else{
mn=l;
mx=r;
add-=(r-l+1);
st[yy].insert({mn,mx});
yy--;
continue;
}
}
else mn=(*it).fi;
}
if(it!=st[yy].end()){
if((*it).se>=l && (*it).fi<=r)mx=max(mx,(*it).se);
}
//~ cout<<add<<" AA "<<yy<<" AA "<<rr<<endl;
while(it!=st[yy].end()){
if((*it).fi>r)break;
if((*it).se<l)continue;
auto it1=it;
it1++;
if(it1==st[yy].end() || (*it).se>=r){
mx=max(mx,(*it).se);
st[yy].erase(it);
break;
}
add-=min(r,(*it1).fi)-max(l,(*it).se);
mx=max(mx,(*it).se);
st[yy].erase(it);
it=it1;
}
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].upper_bound({l,1000000});
int mn=0;
int mx=0;
if(it==st[yy].begin()){
if((*it).fi<=r){
mn=l;
add-=(*it).fi-l;
}
else{
mn=l;
mx=r;
add-=(r-l+1);
st[yy].insert({mn,mx});
yy++;
continue;
}
}
else{
it--;
if((*it).se<l){
it++;
if(it!=st[yy].end() && (*it).fi<=r){
mn=l;
add-=(*it).fi-l;
}
}
else mn=(*it).fi;
}
if(it!=st[yy].end()){
if((*it).se>=l && (*it).fi<=r)mx=max(mx,(*it).se);
}
while(it!=st[yy].end()){
if((*it).fi>r)break;
if((*it).se<l)continue;
auto it1=it;
it1++;
if(it1==st[yy].end() || (*it).se>=r){
mx=max(mx,(*it).se);
st[yy].erase(it);
break;
}
add-=min(r,(*it1).fi)-max(l,(*it).se);
mx=max(mx,(*it).se);
st[yy].erase(it);
it=it1;
}
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 |
3 ms |
5076 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
5076 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
5716 KB |
Output isn't correct |
| 4 |
Incorrect |
15 ms |
5820 KB |
Output isn't correct |
| 5 |
Incorrect |
17 ms |
8276 KB |
Output isn't correct |
| 6 |
Incorrect |
76 ms |
8084 KB |
Output isn't correct |
| 7 |
Incorrect |
43 ms |
14200 KB |
Output isn't correct |
| 8 |
Incorrect |
152 ms |
11364 KB |
Output isn't correct |
| 9 |
Incorrect |
68 ms |
15408 KB |
Output isn't correct |
| 10 |
Incorrect |
195 ms |
12036 KB |
Output isn't correct |
