oj.uz

Submission #844397

# Submission time Handle Problem Language Result Execution time Memory
844397 2023-09-05T12:56:20 Z vjudge1 Spiderman (COCI20_spiderman) C++17
70 / 70
 352 ms 18140 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15192 KB Output is correct
2 Correct 5 ms 15088 KB Output is correct
3 Correct 20 ms 16024 KB Output is correct
4 Correct 43 ms 17492 KB Output is correct
5 Correct 307 ms 16724 KB Output is correct
6 Correct 305 ms 18044 KB Output is correct
7 Correct 349 ms 16480 KB Output is correct
8 Correct 352 ms 16816 KB Output is correct
9 Correct 342 ms 18028 KB Output is correct
10 Correct 339 ms 18140 KB Output is correct