#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int Q;
struct SGTR{
int l;int r;
int len;
int sum;
int lzad;
int lzst;
}tr[500005];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].len=r-l+1;
tr[nw].sum=0;tr[nw].lzad=0;tr[nw].lzst=-1;
if(l==r){return;}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void psh(int nw){
if(tr[nw].lzst!=-1){
int st=tr[nw].lzst;
tr[nw].lzst=-1;
tr[nw].lzad=0;
tr[nw*2].sum=st*tr[nw*2].len;
tr[nw*2].lzst=st;
tr[nw*2].lzad=0;
tr[nw*2+1].sum=st*tr[nw*2+1].len;
tr[nw*2+1].lzst=st;
tr[nw*2+1].lzad=0;
return;
}
int ad=tr[nw].lzad;
tr[nw].lzad=0;
tr[nw*2].sum+=ad*tr[nw*2].len;
if(tr[nw*2].lzst!=-1){
tr[nw*2].lzst+=ad;
}else{
tr[nw*2].lzad+=ad;
}
tr[nw*2+1].sum+=ad*tr[nw*2+1].len;
if(tr[nw*2+1].lzst!=-1){
tr[nw*2+1].lzst+=ad;
}else{
tr[nw*2+1].lzad+=ad;
}
}
void updad(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
tr[nw].sum+=tr[nw].len;
if(tr[nw].lzst!=-1){
tr[nw].lzst++;
}else{
tr[nw].lzad++;
}
return;
}
if(tr[nw].r<l||tr[nw].l>r){
return;
}
psh(nw);
updad(nw*2,l,r);updad(nw*2+1,l,r);
tr[nw].sum=tr[nw*2].sum+tr[nw*2+1].sum;
}
void updst(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
tr[nw].sum=0;
tr[nw].lzst=0;
tr[nw].lzad=0;
return;
}
if(tr[nw].r<l||tr[nw].l>r){
return;
}
psh(nw);
updst(nw*2,l,r);updst(nw*2+1,l,r);
tr[nw].sum=tr[nw*2].sum+tr[nw*2+1].sum;
}
int xar[210];int yar[210];int rar[210];
int ans;
int finl(int y,int g){
if(g<0){return 1e12;}
int l=1;int r=y;
while(l<r){
int mi=l+(r-l)/2;
if( (y-mi)*(y-mi)<=g ){
r=mi;
}else{
l=mi+1;
}
}
return l;
}
int finr(int y,int g){
if(g<0){return -1;}
int l=y;int r=m;
while(l<r){
int mi=l+(r-l+1)/2;
if( (y-mi)*(y-mi)<=g ){
l=mi;
}else{
r=mi-1;
}
}
return l;
}
void solve(int ipl){
updst(1,1,m);
updad(1,1,m);
//cout<<ipl<<endl;
for(int i=1;i<=Q;i++){
int L=finl(yar[i],rar[i]*rar[i]-(xar[i]-ipl)*(xar[i]-ipl));int R=finr(yar[i],rar[i]*rar[i]-(xar[i]-ipl)*(xar[i]-ipl));
if(R>=L){
updst(1,L,R);
}
// cout<<L<<" "<<R<<" "<<tr[1].sum<<endl;
updad(1,1,m);
}
//cout<<tr[1].sum-m<<"hehe\n";
ans+=tr[1].sum-m;
}
signed main(){
cin>>n>>m>>Q;
for(int i=1;i<=Q;i++){
cin>>xar[i]>>yar[i]>>rar[i];
}
buildtr(1,1,m);
ans=0;
for(int i=1;i<=n;i++){
solve(i);
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
340 KB |
Output is correct |
| 2 |
Correct |
16 ms |
404 KB |
Output is correct |
| 3 |
Correct |
16 ms |
504 KB |
Output is correct |
| 4 |
Correct |
123 ms |
1828 KB |
Output is correct |
| 5 |
Correct |
139 ms |
6444 KB |
Output is correct |
| 6 |
Correct |
913 ms |
5588 KB |
Output is correct |
| 7 |
Correct |
384 ms |
12500 KB |
Output is correct |
| 8 |
Correct |
2045 ms |
12600 KB |
Output is correct |
| 9 |
Correct |
730 ms |
12500 KB |
Output is correct |
| 10 |
Correct |
2852 ms |
12596 KB |
Output is correct |
