Submission #644064

#TimeUsernameProblemLanguageResultExecution timeMemory
644064mohammedMonemSpiderman (COCI20_spiderman)C++14
70 / 70
411 ms11384 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...