oj.uz

Submission #844264

# Submission time Handle Problem Language Result Execution time Memory
844264 2023-09-05T11:56:01 Z vjudge1 Spiderman (COCI20_spiderman) C++17
70 / 70
 1037 ms 10428 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();
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8280 KB Output is correct
2 Correct 11 ms 8284 KB Output is correct
3 Correct 270 ms 9316 KB Output is correct
4 Correct 776 ms 10320 KB Output is correct
5 Correct 309 ms 8784 KB Output is correct
6 Correct 898 ms 10428 KB Output is correct
7 Correct 357 ms 8784 KB Output is correct
8 Correct 361 ms 8996 KB Output is correct
9 Correct 1035 ms 9960 KB Output is correct
10 Correct 1037 ms 10064 KB Output is correct