// Aber der schlimmste Fiend, dem du begegnen kannst, wirst du immer dir selber sein
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define int long long int
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define rev reverse
#define all(x) x.begin(),x.end()
#define acc accumulate
#define sz size()
#define MOD 1000000007
#define rall(x) x.rbegin(),x.rend()
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const int N = 1e6 + 5;
int cnt[N];
inline void solve(){
int n, k;
cin >> n >> k;
pair<int, int> a[n];
rep(i, 0, n) cin >> a[i].ff;
rep(i, 0, n) a[i].ss = i;
int ans[n];
sort(a, a+n);
rev(a, a+n);
rep(i, 0, n){
cnt[a[i].ff]++;
}
int say = 0;
rep(i, 0, n){
ans[a[i].ss] = 0;
if(a[i].ff == k){
ans[a[i].ss] = say;
}
cnt[a[i].ff] --;
a[i].ff -= k;
vector<int> v;
for(int j = 1; j <= sqrt(a[i].ff); j++){
if(a[i].ff % j == 0){
v.pb(j);
if(j != (a[i].ff/j)) v.pb(a[i].ff / j);
}
}
for(int j : v) {
if(j <= k) continue;
ans[a[i].ss] += cnt[j];
}
a[i].ff += k;
cnt[a[i].ff]++;
if(a[i].ff > k) say++;
}
rep(i, 0, n) cout << ans[i] << " ";
cout << endl;
}
int32_t main(){
fast_io
int t;
t = 1;
while(t--) solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7256 KB |
Output is correct |
| 2 |
Correct |
7 ms |
7000 KB |
Output is correct |
| 3 |
Correct |
288 ms |
9924 KB |
Output is correct |
| 4 |
Correct |
857 ms |
15164 KB |
Output is correct |
| 5 |
Correct |
337 ms |
10832 KB |
Output is correct |
| 6 |
Correct |
980 ms |
16188 KB |
Output is correct |
| 7 |
Correct |
378 ms |
10620 KB |
Output is correct |
| 8 |
Correct |
378 ms |
10832 KB |
Output is correct |
| 9 |
Correct |
1109 ms |
16072 KB |
Output is correct |
| 10 |
Correct |
1102 ms |
15952 KB |
Output is correct |
