Submission #229229

#	Time	Username	Problem	Language	Result	Execution time	Memory
229229		VEGAnn	Spiderman (COCI20_spiderman)	C++14	70 / 70	480 ms	14444 KiB

spiderman

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
const int N = 300100;
const int M = 1000100;
vector<int> vc;
int n, k, a[M], kol[M], mem[M];
bool was[M];

int main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0);
    
//    freopen("in.txt","r",stdin);
    
    cin >> n >> k;
    
    for (int i = 0; i < n; i++){
        cin >> a[i];
        kol[a[i]]++;
        vc.PB(a[i]);
    }
    
    sort(all(vc));
    
    for (int i = 0; i < n; i++){
        if (a[i] < k) {
            cout << "0 ";
            continue;
        }
        
        if (was[a[i]]){
            cout << mem[a[i]] << " ";
            continue;
        }
        
        int ans = 0;
        
        if (a[i] > k){
            int vl = a[i] - k;
        
            for (int i = 1; i * i <= vl; i++)
                if (vl % i == 0){
                    if (k < i) ans += kol[i];
                
                    if (vl / i != i && k < vl / i)
                        ans += kol[vl / i];
                }
        }  else ans = n - (upper_bound(all(vc), a[i]) - vc.begin());
        
        if (k == 0)
            ans--;
        
        mem[a[i]] = ans;
        was[a[i]] = 1;
        
        cout << ans << " ";
    }
    
    return 0;
}

• Subtask 1: 70 / 70