Submission #487514

#	Time	Username	Problem	Language	Result	Execution time	Memory
487514		ala2	Spiderman (COCI20_spiderman)	C++14	70 / 70	1176 ms	17192 KiB

spiderman

#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 / 70