Una Casa de Minecraft#12216

Una Casa de Minecraft (Editorial)

Autor del Problema:	De3b0o
Preparado por:	De3b0o
Editado por:	Hasan Saleh (MathModel)

Solución

A lo largo de la solución asumiremos que $n \leq m$ n \le m, si no, simplemente podemos rotar la cuadrícula.

No podemos permitirnos simular cada consulta celda por celda. En su lugar, procesamos fila por fila.

Para una fila fija $i$ , considera una consulta $(x, y, d, c, s)$ (x,y,d,c,s). Todas las celdas que satisfacen la primera condición (la condición de distancia) forman un rango $[l, r]$ [l,r].

Así, cada consulta agrega un intervalo en la fila $i$ .

Podemos usar un enfoque de línea de barrido para calcular todos los valores del arreglo $b$ para la fila $i$ .

Para la fila $i$ , creamos eventos en $l$ y $r + 1$ r+1 para el intervalo $[l, r]$ [l,r]. Cada evento significa: "comenzar a agregar esta consulta" o "dejar de agregar esta consulta".

Mantenemos un arreglo de frecuencia $f [c]$ = total $s$ de consultas activas con parámetro $c$ . También mantenemos $s u m =$ suma de todos los $s$ activos.

Al procesar la fila $i$ y la columna $j$ :

Si $a_{i, j} = 0$ a_{i,j}=0, entonces $b_{i, j} = s u m$ b_{i,j}=sum.
De lo contrario, para cada divisor $d$ de $a_{i, j}$ a_{i,j}, agrega $f [d]$ a $b_{i, j}$ b_{i,j}.

En conclusión:

Iteramos sobre todas las filas ( $1 \leq i \leq n$ 1 \le i \le n), para cada fila iteramos sobre todas las consultas y encontramos el rango $[l, r]$ [l,r] para cada consulta. Luego, usando un enfoque de línea de barrido, podemos determinar los valores del arreglo $b$ para esta fila.

Complejidad:

Precomputando divisores: $O (n \cdot m \cdot max A)$ \mathcal{O}(n \cdot m \cdot \sqrt{\max A}).
Para cada fila estamos iterando sobre todas las consultas, así que es $O (n \cdot q)$ \mathcal{O}(n \cdot q).
Para cada celda $(x, y)$ estamos iterando sobre todos los divisores de $a_{x, y}$ a_{x,y}, así que es $O (n \cdot m \cdot max D)$ \mathcal{O}(n \cdot m \cdot \max D).

La complejidad total es $O (n \cdot m \cdot (max A + max D) + n \cdot q)$ \mathcal{O}(n \cdot m \cdot (\sqrt{\max A} + \max D) + n \cdot q), y dado que $n \leq m$ n \le m, entonces $n \leq n \cdot m \leq 320$ n \le \sqrt{n \cdot m} \le 320, $max A$ <= $1 0^{6}$ 10^6, $max D = 240$ \max D = 240.

Haciendo que la peor complejidad total sea $O (3 e 8)$ , lo cual pasa en menos de 4 segundos.

La siguiente es la implementación:


#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
#define double long double
 
using namespace std;

mt19937 rnd(time(0));

const int N = 1e5+9 , NN = 1e6+9;

int q,c[N],se[100LL*N],org,sq[NN];
ll s[N],f[100LL*N],sum;
ll x[N] , y[N] , d[N] , n , m;
bool g,vis[100LL*N];
vector<int> divisors[100LL*N];

ll sqr(ll x)
{
    ll l = 0 , r = min(x,100000LL);
    ll ans;
    while(l<=r)
    {
        if(mid*mid<=x)
            ans=mid,l=mid+1;
        else
            r=mid-1;
    }
    return ans;
}

void factorize(int v)
{
    if(vis[v])
        return;
    vis[v]=1;
    for(ll i = 1 ; v>=i*i ; i++)
    {
        if(v%i==0)
        {
            divisors[v].pb(i);
            if(v/i!=i)
                divisors[v].pb(v/i);
        }
    }
}

int main()
{
    d3
    vis[0]=1;
    for(ll i = 0 ; NN>i ; i++)
        sq[i]=sqr(i);
    for(ll i = 2 ; 100LL*N>i ; i++)
    {
        if(se[i])
            continue;
        se[i]=i;
        for(ll j = i*i ; 100LL*N>j ; j+=i)
        {
            if(se[j])
                continue;
            se[j]=i;
        }
    }
    cin >> n >> m;
    if(n>m)
        swap(n,m),g=1;
    int a[n+1][m+1];
    ll b[n+1][m+1];
    memset(b,0,sizeof(b));
    vector<int> e[m+2];
    if(g)
        swap(n,m),g=0;
    if(n>m)
    {
        g=1;
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cin>>a[j][i];
        }
        swap(n,m);
    }
    else
    {
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cin>>a[i][j];
        }
    }
    for(int i = 1 ; n>=i ; i++)
        for(int j = 1 ; m>=j ; j++)
            factorize(a[i][j]);
    cin >> q;
    for(int qe = 1 ; q>=qe ; qe++)
    {
        cin >> x[qe] >> y[qe] >> d[qe] >> c[qe] >> s[qe];
        d[qe]*=d[qe];
        if(g)
            swap(x[qe],y[qe]);
    }
    ll mo = m*m;
    for(ll i = 1 ; n>=i ; i++)
    {
        ll de;
        int l , r;
        for(int qe = 1 ; q>=qe ; qe++)
        {
            de=d[qe]-(i-x[qe])*(i-x[qe]);
            if(de<0)
                continue;
            if(mo<=de)
                de=m;
            else if(de<NN)
                de=sq[de];
            else
                de=sqr(de);
            l=max(1LL,y[qe]-de);
            r=min(m,y[qe]+de);
            e[l].pb(qe);
            e[r+1].pb(-qe);
        }
        for(int j = 1 ; m+1>=j ; j++)
        {
            for(auto it : e[j])
            {
                if(it<0)
                    f[c[-it]]-=s[-it],sum-=s[-it];
                else
                    f[c[it]]+=s[it],sum+=s[it];
            }
            if(j==m+1)
                break;
            if(a[i][j]==0)
            {
                b[i][j]=sum;
                continue;
            }
            for(auto it : divisors[a[i][j]])
                b[i][j]+=f[it];
        }
        for(int j = 1 ; m+1>=j ; j++)
            e[j].clear();
    }
    if(g)
    {
        swap(n,m);
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cout << b[j][i] << " ";
            lin
        }
    }
    else
    {
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cout << b[i][j] << " ";
            lin
        }
    }
}