Submission #844259

# Submission time Handle Problem Language Result Execution time Memory
844259 2023-09-05T11:54:31 Z vjudge1 Spiderman (COCI20_spiderman) C++17
70 / 70
1025 ms 10820 KB
#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();
}
# Verdict Execution time Memory Grader output
1 Correct 13 ms 8280 KB Output is correct
2 Correct 12 ms 8284 KB Output is correct
3 Correct 268 ms 8924 KB Output is correct
4 Correct 772 ms 10820 KB Output is correct
5 Correct 309 ms 9108 KB Output is correct
6 Correct 890 ms 10464 KB Output is correct
7 Correct 349 ms 8864 KB Output is correct
8 Correct 352 ms 9356 KB Output is correct
9 Correct 1025 ms 10228 KB Output is correct
10 Correct 1022 ms 10016 KB Output is correct