제출 #1284962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284962		hrantsargsyan	Spiderman (COCI20_spiderman)	C++20	70 / 70	1307 ms	10112 KiB

spiderman

// Task Spiderman.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#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)
        {
            if (k == 0)
            {
                cout << cntBaj[h[i]] - 1 << " ";
            }
            else
            {
                cout << cntBaj[h[i] - k] << " ";
            }
            
        }
        else if (h[i] == k)
        {
            cout << cntBaj[h[i] - k] + kcnt << " ";
        }
        else
        {
            cout << 0 << " ";
        }
    }

}

• Subtask 1: 70 / 70