Submission #1284950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284950		hrantsargsyan	Spiderman (COCI20_spiderman)	C++20	56 / 70	1329 ms	10188 KiB

spiderman

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

const int N = 1e6+5;

int cntNum[N], cntBaj[N], mh=0, h[N];
bool visited[N];
int n, k;

void precalc()
{
    for (int i = 1;i <= mh;++i)
    {
        for (int j = 1;j * j <= i;++j)
        {
            if (i % j == 0)
            {
                if (j > k)
                {
                    cntBaj[i] += cntNum[j];
                }                
                if (i / j > k)
                {
                    cntBaj[i] += cntNum[i/j];
                }
            }
            if (j * j == i && j>k)
            {
                cntBaj[i]-=cntNum[j];
            }
        }
    }
}

int main()
{

    cin >> n >> k;
    int kcnt = 0;
    for (int i = 0;i < n;++i)
    {
        cin >> h[i];
        cntNum[h[i]]++;
        if (h[i] > k)
        {
            kcnt++;
        }
        mh = max(mh, h[i]);
    }
    precalc();
    for (int i = 0;i < n;++i)
    {
        if (h[i] > k)
        {
            cout << cntBaj[h[i] - k]<<" ";
        }
        else if (h[i] == k)
        {
            cout << cntBaj[h[i] - k] + kcnt << " ";
        }
        else
        {
            cout << 0 << " ";
        }
    }

}

• Subtask 1: 56 / 70