A Minecraft House#12216

A Minecraft House (Editoryal)

Problem Author:	De3b0o
Prepared by:	De3b0o
Edited by:	Hasan Saleh (MathModel)

Solution

Throughout the solution we're going to be assuming that $n \leq m$ n \le m, if not we can just rotate the grid.

We cannot afford to simulate each query cell by cell. Instead, we process row by row.

For a fixed row $i$ , consider a query $(x, y, d, c, s)$ (x,y,d,c,s). All the cells that satisfy the first condition (the distance condition) form a range $[l, r]$ [l,r].

Thus each query adds an interval on row $i$ .

We can use a sweep line approach to calculate all the values of array $b$ for row $i$ .

For row $i$ , we create events at $l$ and $r + 1$ r+1 for the interval $[l, r]$ [l,r]. Each event means: "start adding this query" or "stop adding this query".

We maintain a frequency array $f [c]$ = total $s$ of active queries with parameter $c$ . We also maintain $s u m =$ sum of all active $s$ .

When processing row $i$ and column $j$ :

If $a_{i, j} = 0$ a_{i,j}=0, then $b_{i, j} = s u m$ b_{i,j}=sum.
Otherwise, for each divisor $d$ of $a_{i, j}$ a_{i,j}, add $f [d]$ to $b_{i, j}$ b_{i,j}.

In conclusion:

we Iterate over all rows ( $1 \leq i \leq n$ 1 \le i \le n), for each row we iterate over all queries and find the range $[l, r]$ [l,r] for each query, Then using a sweep line approach we can determine the values of array $b$ for this row.

Complexity:

Precomputing divisors: $O (n \cdot m \cdot max A)$ \mathcal{O}(n \cdot m \cdot \sqrt{\max A}).
For each row we're iterating over all queries so it's $O (n \cdot q)$ \mathcal{O}(n \cdot q).
For each cell $(x, y)$ we're iterating over all $a_{x, y}$ a_{x,y}'s divisors so it's $O (n \cdot m \cdot max D)$ \mathcal{O}(n \cdot m \cdot \max D).

The total complexity is $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), and since $n \leq m$ n \le m then $n \leq s q r t (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.

Making the worst total complexity $O (3 e 8)$ which passes in under 4 seconds.

The following is the implementation:


#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
        }
    }
}