JLOI2016简要题解

2016.04.28 18:01 Thu | 445次阅读 | 旧日oi | 固定链接 | 源码

D1T1 侦察守卫

题目大意

给出一棵树,有点权无边权。给出一些关键点,要求选择一些点,使得每个关键点都和某个选择的点的距离<=d,求权值和最小的选择方案。n<=500000,d<=20

题解

树形dp,f[i][j]表示以i为根的子树全部覆盖,距离i最近的点的到i的距离为j(可以在子树外)的最小花费,g[i][j]表示以i为根的子树全部覆盖,距离i最近的点的到i的距离为j(只能在子树内)的最小花费。
转移好麻烦。。我也调了好久加了好多细节……看代码吧……

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define inf 0x3f3f3f3f
char getc(){
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read(){
    static char ch;static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return D;
}
int n,m,d;
int g[N][22],f[N][22],w[N];
bool vis[N];
struct edge
{
    int to,next;
}e[N<<1];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
void dfs(int u,int fa)
{
    for(int i=h[u];i;i=e[i].next)
    if(e[i].to!=fa) dfs(e[i].to,u);
    for(int k=1;k<=d+1;k++)
    {
        if(u==1&&k==d+1)
        {
            int fasd=1;
        }
        int tmp=0,mn=inf;bool flag=0;
        for(int v,i=h[u];i;i=e[i].next)
        if((v=e[i].to)!=fa) 
        {
            tmp+=min(k?g[v][k-1]:inf,f[v][min(d+1,k+1)]);
            if(g[v][k-1]<f[v][min(d+1,k+1)]) flag=1;
            if(k&&g[v][k-1]>=f[v][min(d+1,k+1)]) mn=min(mn,g[v][k-1]-f[v][min(d+1,k+1)]);
        }
        f[u][k]=tmp;g[u][k]=tmp;
        if(!flag) g[u][k]+=mn;
        tmp=0;
        if(k==d+1&&!vis[u])
        {
            for(int v,i=h[u];i;i=e[i].next)
            if((v=e[i].to)!=fa) 
            {
                tmp+=g[v][k];
                tmp=min(tmp,inf);
            }
            f[u][k]=min(f[u][k],tmp);
            g[u][k]=min(g[u][k],tmp);
        }
    }
    f[u][0]=g[u][0]=w[u];
    for(int v,i=h[u];i;i=e[i].next)
    if((v=e[i].to)!=fa) 
    {
        f[u][0]+=min(min(g[v][d],g[v][d+1]),f[v][1]);
        g[u][0]+=min(min(g[v][d],g[v][d+1]),f[v][1]);
    }
    for(int k=1;k<=d+1;k++) g[u][k]=min(g[u][k],g[u][k-1]);
    if(vis[u]) f[u][d+1]=g[u][d];
    else f[u][0]=min(f[u][0],g[u][d+1]);
    for(int k=d;k;k--) 
    {
        f[u][k]=min(f[u][k],min(f[u][k+1],f[u][0]));
        f[u][k]=min(f[u][k],min(g[u][d],g[u][d+1]));
    }
    if(vis[u]) g[u][d+1]=inf; 
}
int main()
{
    n=read();d=read();
    for(int i=1;i<=n;i++) w[i]=read();
    m=read();for(int i=1;i<=m;i++) vis[read()]=1;
    for(int u,v,i=1;i<n;i++)
    {
        u=read();v=read();
        ae(u,v);ae(v,u);
    }
    memset(g,0x3f,sizeof(g));
    dfs(1,0);
    int ans=inf;
    for(int i=0;i<=d+1;i++) ans=min(ans,g[1][i]);
    printf("%d\n",ans);
}

D2T2 方

题目大意

给出n*m的点阵,有k个坏点,问能选出多少个正方形使得四个点都在点阵的非坏点上。
n,m<=1e6,k<=2000

题解

没有坏点的话,平行坐标轴的边长为x的正方形内有x个四个角都在边界上的正方形,由此就可以推出k=0时的公式了。
然后考虑去掉有坏点的,枚举坏点,看每个点在多少个正方形的边界,枚举这个点在正方形的哪个边界。然后能列出方程形如x<=a,y<=b,x+y<=c的形式,组合数解一发就好了。
然后考虑去重,如果某个正方形4角中有两个坏点,那么枚举这两个坏点就可以确定这个正方形。
于是我们用k^2的时间枚举每一对坏点,求出以这两个坏点为角的所有正方形,然后计一下数就可以了。

mycode

#include<bits/stdc++.h>
using namespace std;
#define mod 100000007
#define ll long long
#define M 3000005
#define N 2005
int n,m,K;
ll ans;
#define hashmod 1000007
int h[hashmod],nxt[N],tp;
ll X[N],Y[N];
int x[N],y[N],id[N];
void insert(ll x,ll y,int i)
{
    int t=(x*1000000+y)%hashmod;
    X[++tp]=x;Y[tp]=y;nxt[tp]=h[t];id[tp]=i;h[t]=tp;
}
int find(ll x,ll y)
{
    int t=(x*1000000+y)%hashmod;
    for(int i=h[t];i;i=nxt[i])
    if(X[i]==x&&Y[i]==y) return id[i];
    return 0;
}
ll C(ll n)
{   
    if(n<2) return 0;
    return n*(n-1)/2%mod;
}
ll work(int a,int b,int c)
{
    a--;b--;
    return C(a+2)-C(a-b-1+2)-C(a-c-1+2)+C(a-b-1-c-1+2);
}
ll calc(int x,int y)
{
    ll t1=work(m-y,n-x,x);
    t1+=work(y,x,n-x);
    t1+=work(x,m-y,y);
    t1+=work(n-x,y,m-y);
    return (t1%mod+mod)%mod;
}
bool out(int x,int y)
{
    return x<0||x>n||y<0||y>m;
}
int a[10],b[10],num[10];
int check1(int p,int q)
{
    if(a[0]==a[1]) return 0;
    if(a[0]>a[1]) swap(a[0],a[1]),swap(b[0],b[1]);
    if(a[0]==a[1]&&b[0]>b[1]) swap(b[0],b[1]);
    if(b[0]>b[1]) return 0;
    int c=a[1]-a[0],d=b[1]-b[0],k;
    int ret=2,mn=0x3f3f3f3f;
    a[2]=a[0]-d;b[2]=b[0]+c;
    a[3]=a[1]-d;b[3]=b[1]+c;
    for(int i=2;i<4;i++) if(out(a[i],b[i])) return 0;
    if(k=find(a[2],b[2])) ret++,mn=min(mn,k);
    if(k=find(a[3],b[3])) ret++,mn=min(mn,k);
    if(mn<p||mn<q)return 0;
    return ret-1;
}
int check2(int p,int q)
{
    if(b[0]==b[1]) return 0;
    if(b[0]>b[1]) swap(a[0],a[1]),swap(b[0],b[1]);
    if(b[0]==b[1]&&a[0]<a[1]) swap(a[0],a[1]);
    if(a[0]<a[1]) return 0;
    int c=a[0]-a[1],d=b[1]-b[0],k;
    int ret=2,mn=0x3f3f3f3f;
    a[2]=a[0]-d;b[2]=b[0]-c;
    a[3]=a[1]-d;b[3]=b[1]-c;
    for(int i=2;i<4;i++) if(out(a[i],b[i])) return 0;
    if(k=find(a[2],b[2])) ret++,mn=min(mn,k);
    if(k=find(a[3],b[3])) ret++,mn=min(mn,k);
    if(mn<p||mn<q)return 0;
    return ret-1;
}
int check3(int p,int q)
{
    if(a[0]==a[1]) return 0;
    if(a[0]>a[1]) swap(a[0],a[1]),swap(b[0],b[1]);
    if(a[0]==a[1]&&b[0]>b[1]) swap(b[0],b[1]);
    if(b[0]>b[1]) return 0;
    int c=a[1]-a[0],d=b[1]-b[0],k;
    int ret=2,mn=0x3f3f3f3f;
    a[2]=a[0]+d;b[2]=b[0]-c;
    a[3]=a[1]+d;b[3]=b[1]-c;
    for(int i=2;i<4;i++) if(out(a[i],b[i])) return 0;
    if(k=find(a[2],b[2])) ret++,mn=min(mn,k);
    if(k=find(a[3],b[3])) ret++,mn=min(mn,k);
    if(mn<p||mn<q)return 0;
    return ret-1;
}
int check4(int p,int q)
{
    if(b[0]==b[1]) return 0;
    if(b[0]>b[1]) swap(a[0],a[1]),swap(b[0],b[1]);
    if(b[0]==b[1]&&a[0]<a[1]) swap(a[0],a[1]);
    if(a[0]<a[1]) return 0;
    int c=a[0]-a[1],d=b[1]-b[0],k;
    int ret=2,mn=0x3f3f3f3f;
    a[2]=a[0]+d;b[2]=b[0]+c;
    a[3]=a[1]+d;b[3]=b[1]+c;
    for(int i=2;i<4;i++) if(out(a[i],b[i])) return 0;
    if(k=find(a[2],b[2])) ret++,mn=min(mn,k);
    if(k=find(a[3],b[3])) ret++,mn=min(mn,k);
    if(mn<p||mn<q)return 0;
    return ret-1;
}
int check5(int p,int q)
{
    if(a[0]>a[1]) swap(a[0],a[1]),swap(b[0],b[1]);
    if(abs(a[0]-a[1])<abs(b[0]-b[1])) return 0;
    int t=b[1]-b[0],x=a[1]-a[0];
    int k,ret=2,mn=0x3f3f3f3f;
    if((x-t)%2!=0) return 0;
    int y=(x-t)/2;
    b[2]=b[0]-y,a[2]=a[0]+(x-y);
    a[3]=a[1]-(x-y);b[3]=b[1]+y;
    for(int i=2;i<4;i++) if(out(a[i],b[i])) return 0;
    if(k=find(a[2],b[2])) ret++,mn=min(mn,k);
    if(k=find(a[3],b[3])) ret++,mn=min(mn,k);
    if(mn<p||mn<q)return 0;
    return ret-1;
}
int check6(int p,int q)
{
    if(b[0]>b[1]) swap(b[0],b[1]),swap(a[0],a[1]);
    if(abs(b[0]-b[1])<abs(a[0]-a[1])) return 0;
    int t=a[1]-a[0],x=b[1]-b[0];
    int k,ret=2,mn=0x3f3f3f3f;
    if((x-t)%2!=0) return 0;
    int y=(x-t)/2;
    a[2]=a[0]-y,b[2]=b[0]+(x-y);
    a[3]=a[1]+y;b[3]=b[1]-(x-y);
    for(int i=2;i<4;i++) if(out(a[i],b[i])) return 0;
    if(k=find(a[2],b[2])) ret++,mn=min(mn,k);
    if(k=find(a[3],b[3])) ret++,mn=min(mn,k);
    if(mn<p||mn<q)return 0;
    return ret-1;
}
ll calc2(int i,int j)
{
    int sum=0;
    a[0]=x[i];a[1]=x[j];
    b[0]=y[i];b[1]=y[j];
    sum+=check1(i,j);
    sum+=check2(i,j);
    sum+=check3(i,j);
    sum+=check4(i,j);
    sum+=check5(i,j);
    if(abs(x[i]-x[j])!=abs(y[i]-y[j])) sum+=check6(i,j);
    return sum;
}
int main()
{
    cin>>n>>m>>K;
    for(int i=1;i<=min(n,m);i++) 
        (ans+=1ll*(n-i+1)*(m-i+1)%mod*i)%=mod;
    for(int i=1;i<=K;i++) 
    {
        scanf("%d%d",&x[i],&y[i]);
        insert(x[i],y[i],i);
    }
    for(int i=1;i<=K;i++) 
        ans=(ans-calc(x[i],y[i])+mod)%mod;
    int num2=0;
    for(int i=1;i<=K;i++)
    for(int j=i+1;j<=K;j++) 
        ans=(ans+calc2(i,j))%mod;
    printf("%lld\n",ans);
}

D1T3 成绩比较

题目大意

有n个同学m门课,每科成绩的满分是ui,每个人的分数是正整数。其中有一个人的每科成绩的排名为i(指有i-1个人的分数比它高),并且有k个人每科排名都不比这个人高,问有多少种不同的得分方案。
n<=100,m<=100,k<=100,ui<=1000000000,保证有至少一组解。

题解

令f[i][j]表示前i个人,有j个人至少有一科比那个人高的方案数。
则$f[i+t][j+t]=\sum_{k=1}^{ui}{f[i][j]C(j,rk[i]-t-1)C(n-j,t)(u[i]-k)^{rk[i]-1}k^{n-rk[i]}}$
k为这个人这科的分数。
组合数可以预处理,后面那两个东西可以写成一个关于x的多项式,然后只需求出1^k+2^k+...+u[i]^k的值就行了,k<=n
一个拉格朗日插值就可以啦。不会的可以去看我的拉格朗日插值介绍。
复杂度n^3logn

mycode

#include <bits/stdc++.h>
using namespace std;
#define N 105
#define ll long long
#define mod 1000000007
int n,m,K;
int u[N],rk[N];
ll f[N][N],c[N][N],pre[N][N],p[N][N];
ll qpow(ll x,ll k)
{
    ll ret=1;
    while(k)
    {
        if(k&1) ret=ret*x%mod;
        k>>=1;x=x*x%mod;
    }
    return ret;
}
ll calc(ll n,ll k)
{
    static ll y[N];
    for(int i=1;i<=k+2;i++) y[i]=(y[i-1]+qpow(i,k))%mod;
    if(n<=k+2) 
    {
        return y[n];
        return 0;
    }
    ll tmp=1,fin=0,d=1;
    for(int i=2;i<=k+2;i++) d=d*(1-i+mod)%mod; 
    for(int i=1;i<=k+2;i++) tmp=tmp*(n-i)%mod;
    for(int i=1;i<=k+2;i++) 
    {
        fin=(fin+y[i]*tmp%mod*qpow(n-i,mod-2)%mod*qpow(d,mod-2))%mod;
        d=d*qpow(i-k-2+mod,mod-2)%mod*i%mod;
    }
    return fin;
}
ll work(ll rk,ll lim)
{
    static ll a[105];
    memset(a,0,sizeof(a));
    for(int i=0;i<=rk-1;i++)
    {
        a[n-rk+i]=qpow(lim,rk-1-i)*c[rk-1][i]%mod;
        if(i&1) a[n-rk+i]=mod-a[n-rk+i];
    }
    ll ret=0;
    for(int i=n-rk;i<n;i++) (ret+=a[i]*calc(lim,i))%=mod;
    return ret;
}
int main()
{
    cin>>n>>m>>K;
    for(int i=1;i<=m;i++) scanf("%d",&u[i]);
    for(int i=1;i<=m;i++) scanf("%d",&rk[i]);
    f[0][0]=c[0][0]=1;
    for(int i=1;i<=100;i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    for(int i=1;i<=m;i++)
    {
        ll tmp=work(rk[i],u[i]);
        for(int j=0;j<=n;j++)
        if(f[i-1][j])
        {
            for(int t=0;t<n-j&&t<rk[i];t++)
            (f[i][j+t]+=f[i-1][j]*c[n-j-1][t]%mod*c[j][rk[i]-t-1]%mod*tmp)%=mod;
        }
    }
    printf("%lld\n",f[m][n-1-K]);
}

D2T1 字符串覆盖

题目大意

给出一个字符串和其4个子串,问把这4个串放在能原串匹配的位置上,最多能覆盖多长,最少能覆盖多长。

题解

先枚举4个串放置的顺序。O(24)
对于最大值,一定是第2个串的开头恰好在第一个串的结尾前后的能匹配匹配点,后面几个点也是类似,这样O(8)就能算出答案。
对于最小值。枚举第2个串的位置,然后第1个串一定恰好在第二个串开头的前一个匹配点。同理,第4个串的开头也恰好在第3个串开头的后一个匹配点。如果2和3相交,那么一定相交的越多越好,如果不交,那就需要一个树状数组求最小值了。
复杂度mlogm,m为原串长。
总复杂度24mlogm

#include<bits/stdc++.h>
using namespace std;
#define N 20005
int mx,mn;
int T,n,m;
char ss[N],str[N];
int st[5][N],ed[5][N],St[5];
int num[5],len[5],id[5];
int nxt[N];
int pre[5][10005][5];
int nnxt[5][10005][5];
int pree[5][10005][5];
int nnxte[5][10005][5];
int s[5],e[5];
void get_nxt(int len)
{
    int j=1,k=0;
    while(j<=len)
    {
        if(k==0||str[j]==str[k])
        {
            j++;k++;
            nxt[j]=k;
        }
        else k=nxt[k];
    }
}
void work()
{
    int ret=0,last=0;
    for(int i=1;i<=n;i++)
    {
        if(!s[i]||s[i]<s[i-1]) return;
        if(s[i]>last)
        {
            ret+=e[i]-s[i]+1;
            last=e[i];
        }
        else if(e[i]>last)
        {
            ret+=e[i]-last;
            last=e[i];
        }
    }
    mx=max(mx,ret);
    mn=min(mn,ret);
    if(ret==4)
    {
        int fa=1;
    }
}
void check()
{
    s[1]=st[id[1]][1];e[1]=ed[id[1]][1];
    s[n]=st[id[n]][num[id[n]]];e[n]=ed[id[n]][num[id[n]]];
    if(n==2){work();}
    else if(n==3)
    {
        for(int k=nnxt[id[1]][1][id[2]];k<=pre[id[3]][num[id[3]]][id[2]];k++) 
        {
            s[2]=st[id[2]][k],e[2]=ed[id[2]][k];        
            work();
        }
    }
    else if(n==4)
    {
        for(int k=pree[id[1]][1][id[2]];k<=nnxte[id[1]][1][id[2]];k++) 
        for(int t=pree[id[2]][k][id[3]];t<=nnxte[id[2]][k][id[3]];t++)
        {
            s[2]=st[id[2]][k],e[2]=ed[id[2]][k];    
            s[3]=st[id[3]][t],e[3]=ed[id[3]][t];    
            work();
        }
    }
    if(n==2)
    {
        for(int i=1;i<=num[id[1]];i++)
        {
            s[1]=st[id[1]][i];e[1]=ed[id[1]][i];
            s[2]=st[id[2]][nnxt[id[1]][i][id[2]]];
            e[2]=ed[id[2]][nnxt[id[1]][i][id[2]]];
            work();
        }
    }
    else if(n==3)
    {
        for(int k=1;k<=num[id[2]];k++) 
        {
            s[2]=st[id[2]][k],e[2]=ed[id[2]][k];    
            int t1=pre[id[2]][k][id[1]],t2=nnxt[id[2]][k][id[3]];
            if(!t1||t2>num[id[3]]) continue;
            s[1]=st[id[1]][t1];e[1]=ed[id[1]][t1];
            s[3]=st[id[3]][t2];e[3]=ed[id[3]][t2];  
            work();
        }
    }
    else if(n==4)
    {
        for(int t1,i=1;i<=num[id[1]];i++)
        {
            s[1]=st[id[1]][i];e[1]=ed[id[1]][i];
            t1=nnxt[id[1]][i][id[2]];
            s[2]=st[id[2]][t1],e[2]=ed[id[2]][t1];   
            t1=nnxt[id[2]][t1][id[3]]; 
            s[3]=st[id[3]][t1],e[3]=ed[id[3]][t1];
            t1=nnxt[id[3]][t1][id[4]]; 
            s[4]=st[id[4]][t1];e[4]=ed[id[4]][t1]; 
            work();
        }
    }   
}
int main()
{
    for(cin>>T;T--;)
    {
        scanf("%s",ss+1);m=strlen(ss+1);
        cin>>n;
        mn=0x3f3f3f3f;mx=0;
        memset(num,0,sizeof(num));
        for(int i=1;i<=n;i++) 
        {
            scanf("%s",str+1);len[i]=strlen(str+1);
            get_nxt(len[i]);
            int j=1,k=1;
            while(j<=m)
            {
                if(k==0||ss[j]==str[k]) j++,k++;
                else k=nxt[k];
                if(k==len[i]+1) 
                {
                    st[i][++num[i]]=j-len[i];
                    ed[i][num[i]]=j-1;
                    k=nxt[k];
                }
            }
        }
        if(n==1)
        {
            printf("%d %d\n",len[1],len[1]);
            continue;
        }
        for(int i=1;i<=n;i++) st[i][num[i]+1]=ed[i][num[i]+1]=0;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=j)
        {
            for(int t=0,k=1;k<=num[i];k++) 
            {
                while(t<num[j]&&st[i][k]>=st[j][t+1]) t++;
                pre[i][k][j]=t;
            }
            for(int t=num[j]+1,k=num[i];k;k--)
            {
                while(t>1&&st[i][k]<=st[j][t-1]) t--;
                nnxt[i][k][j]=t;
            }
        }    
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        if(i!=j)
        {
            for(int t=0,k=1;k<=num[i];k++) 
            {
                while(t<num[j]&&ed[i][k]>=st[j][t+1]) t++;
                pree[i][k][j]=t;
            }
            for(int t=num[j]+1,k=num[i];k;k--)
            {
                while(t>1&&ed[i][k]<st[j][t-1]) t--;
                nnxte[i][k][j]=t;
            }
        }     
        for(int i=1;i<=n;i++) id[i]=i;
        do{check();}while(next_permutation(id+1,id+n+1));
        printf("%d %d\n",mn,mx);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

D2T2 圆的异或并

题目大意

给出一些不交的圆,如果一个区域被覆盖了奇数遍,加上这个区域的面积,求和。n<=200000

题解

扫描线,从左到右,因为圆不交,所以相对顺序不变,我们可以用平衡树围护每个圆的上下边界在当前扫描线位置的值,之需要存这个圆的函数就好了。碰到一个插入,可以先找出这个圆上边的上边界-下边界的数量,就是这个圆被覆盖的次数。这样加圆删圆就可以了。复杂度nlogn

#include <bits/stdc++.h>
using namespace std;
#define N 400005
#define ll long long
int n,m,tot,cnt,rt;
ll now;
int rnd[N],l[N],r[N],sum[N],val[N],id[N];
struct Circle
{
    ll x,y,r;
    void read(){scanf("%lld%lld%lld",&x,&y,&r);}
    bool operator <(const Circle &a)const{
        return x-r<a.x-a.r;
    }
}c[N];
pair<ll,int> x[N];
void pushup(int x){sum[x]=sum[l[x]]+sum[r[x]]+val[x];}
void lturn(int &k)
{
    int t=r[k];r[k]=l[t];l[t]=k;
    sum[t]=sum[k];pushup(k);k=t;
}
void rturn(int &k)
{
    int t=l[k];l[k]=r[t];r[t]=k;
    sum[t]=sum[k];pushup(k);k=t;
}
double calc(int x,int k)
{
    double tmp=(c[x].x-now)*(c[x].x-now);
    tmp=sqrt(c[x].r*c[x].r-tmp);
    if(k==1) return c[x].y+tmp;
    else return c[x].y-tmp;
}
void insert(int &x,int p,int k)
{
    if(!x)
    {
        x=++cnt;
        rnd[x]=rand();
        sum[x]=val[x]=k;
        id[x]=p;
        return;
    }
    sum[x]+=k;
    if(calc(id[x],val[x])<calc(p,k)||(calc(id[x],val[x])==calc(p,k)&&k>val[x])) 
    {
        insert(l[x],p,k);
        if(rnd[l[x]]<rnd[x]) rturn(x);
    }
    else
    {
        insert(r[x],p,k); 
        if(rnd[r[x]]<rnd[x]) lturn(x);
    }
}
void del(int &x,int p,int k)
{
    if(id[x]==p&&val[x]==k)
    {
        if(!l[x]||!r[x]) x=l[x]+r[x];
        else if(rnd[l[x]]<rnd[r[x]]) rturn(x),del(x,p,k);
        else lturn(x),del(x,p,k);
        return;
    }
    sum[x]-=k;
    if(calc(id[x],val[x])<calc(p,k)||(calc(id[x],val[x])==calc(p,k)&&k>val[x])) 
        del(l[x],p,k);
    else del(r[x],p,k); 
}
int find(int v)
{
    int x=rt,ans=0;
    while(x)
    {
        if(calc(id[x],val[x])>v)
        {
            ans+=sum[l[x]]+val[x];
            x=r[x];
        }
        else x=l[x];
    }
    return ans;
}
ll ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        c[i].read();
        x[++tot]=make_pair(c[i].x-c[i].r,i);
        x[++tot]=make_pair(c[i].x+c[i].r,-i);
    }
    sort(x+1,x+tot+1);
    for(int i=1;i<=tot;i++)
    {
        now=x[i].first;
        if(x[i].second>0)
        {
            int k=find(c[x[i].second].y);
            if(~k&1) ans+=c[x[i].second].r*c[x[i].second].r;
            else ans-=c[x[i].second].r*c[x[i].second].r;
            insert(rt,x[i].second,1);
            insert(rt,x[i].second,-1);
        }
        else
        {
            del(rt,-x[i].second,1);
            del(rt,-x[i].second,-1);
        }
    }
    printf("%lld\n",ans);
}