Submission #844397

#	Time	Username	Problem	Language	Result	Execution time	Memory
844397		vjudge1	Spiderman (COCI20_spiderman)	C++17	70 / 70	352 ms	18140 KiB

spiderman

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1e6 + 5, MOD = 1e9 + 7;

ll cnt[N], ans[N];
map<ll, ll> mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, k, a = 0;
    cin >> n >> k;
    
    vector<int> vec(n);

    for(int i = 0; i < n; i++)
    {
        cin >> vec[i];
        cnt[vec[i]]++;

        if(vec[i] > k)
            a++;
    }    

    ans[0] = a;

    for(int i = k + 1; i <= 1e6; i++)
    {
        ll x = i - k;
        if(cnt[i])
        {
            for(ll j = 1; j * j <= x; j++)
            {
                if(x % j == 0)
                {
                    if(j > k)
                    {
                        ans[x] += cnt[j] - (j == i ? 1 : 0);
                    }
                    if(x / j != j and x / j > k)
                    {
                        ans[x] += cnt[x / j] - (x / j == i ? 1 : 0);
                    }
                }
            }
        }
    }

    for(int i = 0; i < n; i++)
    {
        if(vec[i] < k)
            cout << 0 << " ";
        else
            cout << ans[vec[i] - k] << " ";
    }

    cout << '\n';
}

• Subtask 1: 70 / 70