Submission #844303

#	Time	Username	Problem	Language	Result	Execution time	Memory
844303		vjudge1	Spiderman (COCI20_spiderman)	C++14	56 / 70	1138 ms	30324 KiB

spiderman

// 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 seg[4*N];
int find(int i, int l, int r, int ql, int qr){
    if(l > qr || r < ql) return 0;
    if(l >= ql && r <= qr) return seg[i];
    int m = (l+r) / 2;
    return find(i*2, l, m, ql, qr) + find(i*2+1, m+1, r, ql, qr);
}
void up(int i, int l, int r, int p){
    if(l > p || r < p) return;
    if(l == r){
        seg[i]++;
        return;
    }
    int m = (l+r) / 2;
    up(i*2, l, m, p);
    up(i*2+1, m+1, r, p);
    seg[i] = seg[i*2] + seg[i*2+1];
}
inline void solve(){
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int &i : a) cin >> i;
    int cnt[N];
    rep(i, 0, N) cnt[i] = 0;
    int ans[n];
    rep(i, 0, n){
        up(1, 1, N, a[i]);
        cnt[a[i]]++;
    }
    for(int i = n-1; i > -1; i--){
        ans[i] = 0;
        if(a[i] == k){
            ans[i] = find(1, 1, N, a[i]+1, N);
        }
        a[i] -= k;
        vector<int> v;
        for(int j = 1; j <= sqrt(a[i]); j++){
            if(a[i] % j == 0){
                if(j != 1 && j != sqrt(a[i])) v.pb(j);
                v.pb(a[i] / j);
            }
        }
        for(int j : v) {
            if(j <= k) continue;
            ans[i] += cnt[j];
        }
        a[i] += k;
    }
    rep(i, 0, n) cout << ans[i] << " ";
    cout << endl;
}
int32_t main(){
    fast_io
    int t;
    t = 1;
    while(t--) solve();
}

• Subtask 1: 56 / 70