oj.uz

Submission #639047

# Submission time Handle Problem Language Result Execution time Memory
639047 2022-09-08T11:39:11 Z xad Spiderman (COCI20_spiderman) C++14
70 / 70
 1123 ms 10536 KB 
#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.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2644 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 294 ms 4764 KB Output is correct
4 Correct 864 ms 8792 KB Output is correct
5 Correct 340 ms 6220 KB Output is correct
6 Correct 982 ms 10536 KB Output is correct
7 Correct 383 ms 6160 KB Output is correct
8 Correct 384 ms 6160 KB Output is correct
9 Correct 1111 ms 10444 KB Output is correct
10 Correct 1123 ms 10424 KB Output is correct