oj.uz

Submission #644064

# Submission time Handle Problem Language Result Execution time Memory
644064 2022-09-23T17:31:26 Z mohammedMonem Spiderman (COCI20_spiderman) C++14
70 / 70
 411 ms 11384 KB 
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
[[maybe_unused]] typedef long long ll;
[[maybe_unused]] const int N = (int)1e6 + 54;
[[maybe_unused]] const int mod = (int)1e9 + 7;
[[maybe_unused]] char space = ' ';

void Run(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
#endif
}
int n,k;
vector<int> isPrime(N,1);
vector<int> primes;
ll fastPow(ll x,ll y) {
    if (y == 0) {
        return 1;
    }
    return fastPow(x,y / 2) * fastPow(x,y / 2) * (y % 2 ? x : 1);
}
void sieve() {
    isPrime[0] = isPrime[1] = 0;
    for (ll i = 2; i * i <= N; i++) {
        if (!isPrime[i]) {
            continue;
        }
        for (ll j = i * i; j * j <= N; j += i) {
            isPrime[j] = 0;
        }
        primes.push_back(int(i));
    }
}
vector<int> freq(N);
vector<int> ans;
map<int,int> primeDiv;
vector<int> divs;
void div(map<int,int> ::iterator i = primeDiv.begin(),int res = 1,int h = 0) {
    if (i == primeDiv.end()) {
        divs.push_back(res);
        return;
    }
    auto temp = i;
    temp++;
    for (int j = 0; j <= i -> second; j++) {
        div(temp,res * fastPow(i -> first,j));
    }
}
void add(int h) {
    primeDiv.clear();
    divs.clear();
    int temp = h;
    for (const auto &item: primes) {
        while (temp % item == 0) {
            primeDiv[item]++;
            temp /= item;
        }
    }
    if (temp != 1) {
        primeDiv[temp]++;
    }
    div(primeDiv.begin(),1,h);
}

int main()
{
    Run();
    //pre
    sieve();

    //in
    int t = 1;
//    cin >> t;
    while (t--) {
        cin >> n >> k;
        vector<int> h(n);
        for (int i = 0; i < n; i++) {
            cin >> h[i];
        }

        //ops
        ans.resize(n);
        int cnt = 0;
        for (const auto &item: h) {
            freq[item] += item > k;
        }
        for (int i = 0; i < n; i++) {
            if (h[i] > k) {
                cnt++;
                add(h[i] - k);
                for (const auto &item: divs) {
                    ans[i] += freq[item];
                }
            }
        }

        //out
        for (int i = 0; i < n; i++) {
            cout << ans[i] + cnt * (h[i] == k) - (k == 0) << space;
        }
    }

    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8192 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 131 ms 9200 KB Output is correct
4 Correct 378 ms 11384 KB Output is correct
5 Correct 138 ms 9060 KB Output is correct
6 Correct 411 ms 11340 KB Output is correct
7 Correct 142 ms 9068 KB Output is correct
8 Correct 140 ms 9060 KB Output is correct
9 Correct 398 ms 11272 KB Output is correct
10 Correct 393 ms 11128 KB Output is correct