oj.uz

답안 #779275

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
779275 2023-07-11T09:44:20 Z 1075508020060209tc NLO (COCI18_nlo) C++14
110 / 110
 2852 ms 12600 KB 
#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;


}

Subtask #1
110.0 / 110.0

# 결과 실행 시간 메모리 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