Submission #1284897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284897		paronmanukyan	Spiderman (COCI20_spiderman)	C++20	70 / 70	643 ms	124836 KiB

spiderman

#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define no_el(x, y) x.find(y) == x.end()
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO                                                                 \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(nullptr);                                                            \
  cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
#define repl(a, b, c, d) for (int a = b; a >= c; a -= d)

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());

const int MX = 1e6 + 1;
V<int> divs[MX];
int cnt[MX], suf[MX];

void prec() {
    rep(i, 1, MX - 1, 1) {
        rep(j, i, MX - 1, i) {
            divs[j].pb(i);
        }
    }
}

int main()
{
	FASTIO
	prec();
    int n, k; cin >> n >> k;
    V<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    rep(i, 1, n, 1) {
        ++cnt[a[i]];
    }
    suf[MX - 1] = cnt[MX - 1];
    repl(i, MX - 2, 1, 1) {
        suf[i] = suf[i + 1] + cnt[i];
    }

    rep(i, 1, n, 1) {
        if (a[i] < k) {
            cout << 0 << " ";
            continue;
        }
        if (a[i] == k) {
            cout << suf[k + 1] << " ";
            continue;
        }
        int cur = 0;
        for (auto j : divs[a[i] - k]) {
            if (j > k) {
                cur += cnt[j];
            } 
        }
        if (k == 0) --cur;
        cout << cur << " ";
    }
}

• Subtask 1: 70 / 70