oj.uz

Submission #844352

# Submission time Handle Problem Language Result Execution time Memory
844352 2023-09-05T12:33:08 Z vjudge1 Spiderman (COCI20_spiderman) C++17
63 / 70
 1262 ms 23780 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define pb push_back
#define int long long
using namespace std;

const int inf = 2e18 + 5;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;

int32_t main(){
  //freopen("in.txt","r", stdin);
  int n, k;
  cin>>n>>k;
  vector<pair<int, int> > h(n);
  for(int i = 0; i < n; i++){
    cin>>h[i].first;
    h[i].second = i;
  }
  sort(h.begin(), h.end());
  vector<int> ans(n);
  map<int, int> mp;

  if(k > 0){
    for(int i = 0; i < n; i++){
    if(h[i].first < k){
        ans[h[i].second] = 0;
    }
    else if(h[i].first == k){
        ans[h[i].second] = (n - i - 1);
    }
    else{
        int x = h[i].first - k, cnt = 0;

        for(int j = 1; j * j <= x; j++){
            if(x%j == 0){
                if(j > k) cnt += mp[j];
                if(x/j != j && x/j > k) cnt += mp[x/j];
                //if(x == 6) cout<<j<<" "<<x/j<<" "<<mp[j]<<" "<<mp[x/j]<<" "<<cnt<<endl;
            }
        }

        ans[h[i].second] = cnt;
    }
    mp[h[i].first]++;
  }
  }
  else{
    for(int i = 0; i < n; i++) mp[h[i].first]++;

    for(int i = 0; i < n; i++){
      int x = h[i].first - k, cnt = 0;

        for(int j = 1; j * j <= x; j++){
            if(x%j == 0){
                if(j > k) cnt += mp[j];
                if(x/j != j && x/j > k) cnt += mp[x/j];
                //if(x == 6) cout<<j<<" "<<x/j<<" "<<mp[j]<<" "<<mp[x/j]<<" "<<cnt<<endl;
            }
        }

    ans[h[i].second] = cnt - 1;
    }
  }

  for(int i = 0; i < n; i++){
    cout<<ans[i]<<" ";
  }
  cout<<endl;
  return 0;
}

Subtask #1
63.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Incorrect 307 ms 3576 KB Output isn't correct
4 Correct 860 ms 9124 KB Output is correct
5 Correct 514 ms 12496 KB Output is correct
6 Correct 1262 ms 17212 KB Output is correct
7 Correct 506 ms 18512 KB Output is correct
8 Correct 527 ms 18624 KB Output is correct
9 Correct 1245 ms 23776 KB Output is correct
10 Correct 1244 ms 23780 KB Output is correct