Submission #639047

#	Time	Username	Problem	Language	Result	Execution time	Memory
639047		xad	Spiderman (COCI20_spiderman)	C++14	70 / 70	1123 ms	10536 KiB

spiderman

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_pbds ;
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define intt int t; cin>>t; while(t--)
#define emp emplace_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

//#define a first
//#define b second
typedef long long ll;
int f[1000001];
signed main()
{
    x_x
int n,k; cin>>n>>k; pair<int,int> ar[n]; int fans[n];
for(int i=0; i<n; i++)cin>>ar[i].first,ar[i].second=i,fans[i]=0, f[ar[i].first]++;
sort(ar,ar+n);
for(int i=0; i<n; i++)
{
    if(k>ar[i].first)continue;

    f[ar[i].first]--;
     if(k==ar[i].first)
    {
        int l=i,r=n-1,mid,ans=n;
        while(l<=r)
        {
            mid=l+(r-l)/2;
            if(ar[mid].first>ar[i].first)
                ans=mid, r=mid-1;
            else
                l=mid+1;
        }
        fans[ar[i].second]=n-ans;
    }
    else
    {
        int j=ar[i].first-k;
        for(int x=1; (x*x)<=j; x++)
        {
            if(j%x==0)
            {
                if(ar[i].first%x==k)fans[ar[i].second]+=f[x];
                if(((j/x)!=x)&&ar[i].first%(j/x)==k)
                    fans[ar[i].second]+=f[j/x];
            }

        }
    }

    f[ar[i].first]++;
}
  for(auto&i:fans)cout<<i<<' ';
return 0;
}

• Subtask 1: 70 / 70