제출 #1284953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284953		hrantsargsyan	Spiderman (COCI20_spiderman)	C++20	56 / 70	1306 ms	10012 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 (k == 0)
        {
            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 << " ";
        }
    }

}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

• Subtask 1: 56 / 70