oj.uz

Submission #844446

# Submission time Handle Problem Language Result Execution time Memory
844446 2023-09-05T13:14:48 Z vjudge1 Spiderman (COCI20_spiderman) C++17
70 / 70
 134 ms 27264 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 1e6 + 5;

vector<ll> A, A2;
ll divCnt[MAXN], newCnt[MAXN];
map<ll,ll> mp;
int main() {
	fast
	ll N, K;
	cin >> N >> K;

	A = vector<ll>(N+1);
	A2 = vector<ll>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		mp[A[i]]++;
		A2[i] = A[i];
	}
	sort(A2.begin(), A2.end());

	for (int i = 1; i <= N; i++)
		divCnt[A[i]]++;

	for (int i = K+1; i < MAXN; i++) {
		if (divCnt[i] == 0)
			continue;
		for (int j = i; j < MAXN; j+=i) {
			newCnt[j] += divCnt[i];
		}
	}

	for (int i = 1; i <= N; i++) {
		if (A[i] == K) {
			int Q = upper_bound(A2.begin(), A2.end(), A[i]) - A2.begin();
			cout << N - Q + 1 << " ";
		} else if (A[i] < K)
			cout << "0 ";
		else {
			ll ans = newCnt[A[i] - K];
			if (K == 0)
				ans--;
			cout << ans << " ";
		}
	}
	cout << "\n"; 
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15448 KB Output is correct
2 Correct 6 ms 15196 KB Output is correct
3 Correct 26 ms 17244 KB Output is correct
4 Correct 66 ms 21060 KB Output is correct
5 Correct 62 ms 24144 KB Output is correct
6 Correct 134 ms 27264 KB Output is correct
7 Correct 61 ms 24024 KB Output is correct
8 Correct 64 ms 24148 KB Output is correct
9 Correct 129 ms 27120 KB Output is correct
10 Correct 126 ms 27084 KB Output is correct