Submission #844264

#	Time	Username	Problem	Language	Result	Execution time	Memory
844264		vjudge1	Spiderman (COCI20_spiderman)	C++17	70 / 70	1037 ms	10428 KiB

spiderman

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
void solve(){
        int n,k;cin >> n >> k;
        int arr[n],cnt[N],bigger[N];
        memset(cnt , 0 , sizeof(cnt));
        memset(bigger , 0 , sizeof(bigger));
        for(int i = 0;i<n;i++){
                cin >> arr[i];
                cnt[arr[i]]++;
                bigger[arr[i]]++;
        }
        for(int i = N-2;i>=0;i--){
                bigger[i] += bigger[i+1];
        }
        for(int i = 0;i<n;i++){
                int ans = 0;
                //bigger
                if(arr[i] == k)ans = bigger[arr[i]+1];
                //smaller
                cnt[arr[i]]--;
                int temp = arr[i] - k;
                for(int i = 1;i*i<=temp;i++){
                        if(temp % i == 0){
                                if(i > k)ans += cnt[i];
                                if((temp/i) != i and (temp/i) > k)ans += cnt[temp / i];
                        }
                }
                cnt[arr[i]]++;
                cout << ans<< " ";
        }
        cout << endl;   
}
signed main(){
        ios_base::sync_with_stdio(0);cin.tie(0);
        int testcase = 1;//cin >> testcase;
        while(testcase--)solve();
}

• Subtask 1: 70 / 70