Minecraft Evi#12216

Minecraft Evi (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Həll boyunca $n \leq m$ n \le m olduğunu qəbul edəcəyik, əgər belə deyilsə, sadəcə şəbəkəni döndərə bilərik.

Hər sorğunu hüceyrə-hüceyrə simulyasiya etməyə imkanımız yoxdur. Bunun əvəzinə, sətir-sətir işləyirik.

Müəyyən bir $i$ sətiri üçün, $(x, y, d, c, s)$ (x,y,d,c,s) sorğusunu nəzərə alın. Birinci şərti (məsafə şərti) ödəyən bütün hüceyrələr $[l, r]$ [l,r] aralığını formalaşdırır.

Beləliklə, hər sorğu $i$ sətirində bir interval əlavə edir.

Biz $b$ massivinin bütün dəyərlərini $i$ sətiri üçün hesablamaq üçün sürüşdürmə xətti yanaşmasından istifadə edə bilərik.

$i$ sətiri üçün, $[l, r]$ [l,r] intervalı üçün $l$ və $r + 1$ r+1-də hadisələr yaradırıq. Hər bir hadisə deməkdir: "bu sorğunu əlavə etməyə başlayın" və ya "bu sorğunu əlavə etməyi dayandırın".

Biz $f [c]$ = aktiv sorğuların c parametri ilə toplam $s$ -ni saxlayırıq. Həmçinin $s u m =$ bütün aktiv $s$ -lərin cəmini saxlayırıq.

$i$ sətirini və $j$ sütununu işləyərkən:

Əgər $a_{i, j} = 0$ a_{i,j}=0, o zaman $b_{i, j} = s u m$ b_{i,j}=sum.
Əks halda, $a_{i, j}$ a_{i,j}-nin hər bir böləni $d$ üçün, $b_{i, j}$ b_{i,j}-yə $f [d]$ əlavə edin.

Nəticədə:

Biz bütün sətirləri ( $1 \leq i \leq n$ 1 \le i \le n) dövr edirik, hər sətir üçün bütün sorğulara dövr edirik və hər sorğu üçün $[l, r]$ [l,r] aralığını tapırıq, sonra sürüşdürmə xətti yanaşması ilə bu sətir üçün $b$ massivinin dəyərlərini müəyyən edə bilərik.

Komplekslik:

Bölənlərin əvvəlcədən hesablanması: $O (n \cdot m \cdot max A)$ \mathcal{O}(n \cdot m \cdot \sqrt{\max A}).
Hər sətir üçün bütün sorğulara dövr etdiyimiz üçün $O (n \cdot q)$ \mathcal{O}(n \cdot q).
Hər hüceyrə $(x, y)$ üçün bütün $a_{x, y}$ a_{x,y}-nin bölənlərinə dövr etdiyimiz üçün $O (n \cdot m \cdot max D)$ \mathcal{O}(n \cdot m \cdot \max D).

Ümumi komplekslik $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)-dir, və $n \leq m$ n \le m olduğundan $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.

Ən pis ümumi komplekslik $O (3 e 8)$ -dir ki, bu da 4 saniyədən az bir müddətdə keçir.

Aşağıda implementasiya var:


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