oj.uz

Submission #487514

# Submission time Handle Problem Language Result Execution time Memory
487514 2021-11-15T19:48:53 Z ala2 Spiderman (COCI20_spiderman) C++14
70 / 70
 1176 ms 17192 KB 
#include <bits/stdc++.h>

using namespace std;
int v[1001000];
int a[1000100];
int vv[1000100];
int ans[1001000];
int aa[1001000];
int main()
{
    int n;
    cin>>n;
    int k;
    cin>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        vv[a[i]]+=1;
        aa[i]=a[i];
    }
    sort(a,a+n);
    int ans1=0;
    for(int i=0;i<n;i++)
    {
        ans1=0;
        int x=a[i]-k;
        for(int j=1;j*j<=a[i]-k;j++)
        {
            if(x%j==0)
            {
                if(j>k)
                ans1+=v[j];
                if(x/j>k&&x/j<a[i]&&j*j!=x)
                ans1+=v[x/j];
            }
        }
        if(a[i]==k)
        {
            ans1+=n-1-i-vv[a[i]]+1;
        }
        vv[a[i]]--;
        v[a[i]]++;
        ans[a[i]]=ans1;
      //  cout<<"        "<<a[i]<<" "<<ans1<<endl;
    }
    for(int i=0;i<1e6+1;i++)
    {
        if(v[i]>1&&k==0)
        {
            ans[i]+=((v[i]-1));
        }

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


}
/*
5 4
5 13 14 18 22
*/

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7248 KB Output is correct
2 Correct 9 ms 4636 KB Output is correct
3 Correct 310 ms 9064 KB Output is correct
4 Correct 895 ms 12380 KB Output is correct
5 Correct 365 ms 13656 KB Output is correct
6 Correct 1022 ms 17192 KB Output is correct
7 Correct 412 ms 13608 KB Output is correct
8 Correct 406 ms 13688 KB Output is correct
9 Correct 1176 ms 17080 KB Output is correct
10 Correct 1176 ms 17092 KB Output is correct